快捷導(dǎo)航

基于malloc與free函數(shù)的實(shí)現(xiàn)代碼及分析

更新時(shí)間：2013年05月04日 09:38:54 作者：

本篇文章介紹了malloc與free函數(shù)的實(shí)現(xiàn)代碼及分析。需要的朋友參考下

　　用于內(nèi)存管理的malloc與free這對(duì)函數(shù)，對(duì)于使用C語言的程序員應(yīng)該很熟悉。前段時(shí)間聽說有的IT公司以“實(shí)現(xiàn)一個(gè)簡(jiǎn)單功能的malloc”作為面試題，正好最近在復(fù)習(xí)K&R，上面有所介紹，因此花了些時(shí)間仔細(xì)研究了一下。畢竟把題目做出來是次要的，了解實(shí)現(xiàn)思想、提升技術(shù)才是主要的。本文主要是對(duì)malloc與free實(shí)現(xiàn)思路的介紹，藍(lán)色部分文字是在個(gè)人思考中覺得比較核心的東西；另外對(duì)于代碼的說明，有一些K&R上的解釋，使用綠色加亮。

　　在研究K&R第八章第五節(jié)的實(shí)現(xiàn)之前，不妨先看看其第五章第四節(jié)的alloc/afree實(shí)現(xiàn)，雖然這段代碼主要目的是展示地址運(yùn)算。

復(fù)制代碼代碼如下:

alloc實(shí)現(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;
}

　　這種簡(jiǎn)單實(shí)現(xiàn)的缺點(diǎn)：

　　　　1.作為代表內(nèi)存資源的allocbuf，其實(shí)是預(yù)先分配好的，可能存在浪費(fèi)。

　　　　2.分配和釋放的順序類似于棧，即“后進(jìn)先出”，釋放時(shí)如果不按順序會(huì)造成異常。

　　這個(gè)實(shí)現(xiàn)雖然比較簡(jiǎn)陋，但是依然提供了一個(gè)思路。如果能把這兩個(gè)缺點(diǎn)消除，就能夠?qū)崿F(xiàn)比較理想的malloc/free。

　　僅僅依靠地址運(yùn)算來進(jìn)行定位，是限制分配回收靈活性的原因，它要求已使用部分和未使用部分必須通過某個(gè)地址分開成兩個(gè)相鄰區(qū)域。為了能讓這兩個(gè)區(qū)域能夠互相交錯(cuò)，甚至其中還包括一些沒有分配的地址空間，需要使用指針把同類的內(nèi)存空間連接起來形成鏈表，這樣就可以處理地址不連續(xù)的一系列內(nèi)存空間。但是為什么只連接了空閑空間而不連接使用中的空間？這么問可能出于在對(duì)圖中二者類比時(shí)的直覺而沒有經(jīng)過思考，這很簡(jiǎn)單，因?yàn)闆]有必要。前者相互鏈接是為了能夠在內(nèi)存分配時(shí)遍歷所有空閑空間，并且在使用free()回收已使用空間時(shí)進(jìn)行重新插入。而對(duì)于使用中的空間，由于我們?cè)诜峙淇臻g時(shí)已經(jīng)知道它們的地址了，回收時(shí)可以直接告訴free()，并不用像malloc()時(shí)進(jìn)行遍歷。

　　既然提到了鏈表，可能對(duì)數(shù)據(jù)結(jié)構(gòu)稍有了解的人會(huì)立刻寫下一個(gè)struct來代表一個(gè)內(nèi)存區(qū)域，其中包含一個(gè)指向下一個(gè)內(nèi)存區(qū)域的指針，但是這個(gè)struct的其他成員該怎么寫呢？作為待分配的內(nèi)存區(qū)域，大小是不定的，如果把它聲明為struct的成員變量顯然不妥；如果聲明為一個(gè)指向某個(gè)其他的區(qū)域的指針，這似乎又和上面的直觀表示不相符合。（當(dāng)然，這么做也是可以實(shí)現(xiàn)的，它看上去是介于上圖的兩者之間，把管理結(jié)構(gòu)和實(shí)際分配的空間相剝離，在文末我會(huì)專門的討論一下這種實(shí)現(xiàn)方法）因此，這里仍然把控制結(jié)構(gòu)和空閑空間相分開，但保持它們?cè)趦?nèi)存地址中相鄰，形成下圖的形式，而正由這個(gè)特點(diǎn)，我們可以利用對(duì)控制結(jié)構(gòu)指針的指針運(yùn)算來定位對(duì)應(yīng)的內(nèi)存區(qū)域：

　　對(duì)應(yīng)地，把控制信息定義為Header：

復(fù)制代碼代碼如下:

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;

　　使用union而不是直接使用struct的原因是為了地址對(duì)齊。這里是long對(duì)齊，union的x永遠(yuǎn)不會(huì)使用。

　　這樣，malloc的主要工作就是對(duì)這些Header和其后的內(nèi)存塊的管理。

復(fù)制代碼代碼如下:

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 */
    }
}

　　實(shí)際分配的空間是Header大小的整數(shù)倍，并且多出一個(gè)Header大小的空間用于放置Header。但是直觀來看這并不是nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1啊？如果用(nbytes+sizeof(Header))/sizeof(Header)+1豈不是剛好？其實(shí)不是這樣，如果使用后者，nbytes+sizeof(Header)%sizeof(Header) == 0時(shí)，又多分配了一個(gè)Header大小的空間了，因此還要在小括號(hào)里減去1，這時(shí)才能符合要求。

　　malloc()第一次調(diào)用時(shí)建立一個(gè)退化鏈表base，只有一個(gè)大小是0的空間，并指向它自己。freep用于標(biāo)識(shí)空閑鏈表的某個(gè)元素，每次查找時(shí)可能發(fā)生變化；中間的查找和分配過程是基本的鏈表操作，在空閑鏈表中不存在合適大小的空閑空間時(shí)調(diào)用morecore()獲得更多內(nèi)存空間；最后的返回值是空閑空間的首地址，即Header之后的地址，這個(gè)接口與庫(kù)函數(shù)一致。

復(fù)制代碼代碼如下:

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)申請(qǐng)更多的可用空間，并加入。由于調(diào)用了sbrk()，系統(tǒng)開銷比較大，為避免morecore()本身的調(diào)用次數(shù)，設(shè)定了一個(gè)NALLOC，如果每次申請(qǐng)的空間小于NALLOC，就申請(qǐng)NALLOC大小的空間，使得后續(xù)malloc()不必每次都需要調(diào)用morecore()。對(duì)于sbrk()，在后面會(huì)有介紹。

　　這里有個(gè)讓人驚訝的地方：malloc()調(diào)用了morecore()，morecore()又調(diào)用了free()！第一次看到這里時(shí)可能會(huì)覺得不可思議，因?yàn)榘凑諔T性思維，malloc()和free()似乎應(yīng)該是相互分開的，各司其職??？但請(qǐng)?jiān)偎伎家幌拢?SPAN style="COLOR: #0000ff">free()是把空閑鏈表進(jìn)行擴(kuò)充，而malloc()在空閑鏈表不足時(shí)，從系統(tǒng)申請(qǐng)到更多內(nèi)存空間后，也要先把它們轉(zhuǎn)化成空閑鏈表的一部分，再進(jìn)行利用。這樣，malloc()調(diào)用free()完成后面的工作也是順理成章了。根據(jù)這個(gè)思想，后面是free()的實(shí)現(xiàn)。在此之前，還有幾個(gè)morecore()自身的細(xì)節(jié)：

　　1.如果系統(tǒng)也沒有空間可以分配，sbrk()返回-1。cp是char *類型，在有的機(jī)器上char無符號(hào)，這里需要一次強(qiáng)制類型轉(zhuǎn)換。

　　2.morecore()調(diào)用的返回值看上去比較奇怪，別擔(dān)心，freep會(huì)在free()中修改的。使用這個(gè)返回值也是為了在malloc()里的判斷、p = freep的再次賦值的語句能夠緊湊。

復(fù)制代碼代碼如下:

free()

void free(void *ap)
{
    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對(duì)應(yīng)的bp與空閑鏈表的相對(duì)位置，找到它的的最近的上一個(gè)和下一個(gè)空閑空間，或是當(dāng)它在整個(gè)空閑空間的前面或后面時(shí)找到空閑鏈表的首尾元素。注意，由于malloc()的分配方式和free()的回收時(shí)的合并方式（下文馬上要提到），可以保證整個(gè)空閑空間的鏈表總是從低地址逐個(gè)升高，在最高地址的空閑空間回指向低地址第一個(gè)空閑空間。

　　定位后，根據(jù)要釋放的空間與附近空間的相鄰性，進(jìn)行合并，也即修改對(duì)應(yīng)空間的Header。兩個(gè)if并列可以使得bp可以同時(shí)與高地址和低地址空閑空間結(jié)合（如果都相鄰），或者進(jìn)行二者之一的合并，或者不合并。

　　完成了這三部分代碼后（注意放到同一源文件中,sbrk()需要#include <unistd.h>），就可以使用了。當(dāng)然要注意，命名和stdlib.h中的同名函數(shù)是沖突的，可以自行改名。

　　第一次審視源碼，會(huì)發(fā)現(xiàn)很多實(shí)現(xiàn)可能原先并沒有想到：Header的結(jié)構(gòu)和對(duì)齊填充、空間的取整、鏈表的操作和初始化（邊界情況）、malloc()對(duì)free()的調(diào)用、由malloc()和free()暗中保證的鏈表地址有序等等，確實(shí)很值得玩味。另外再附上前文中提到的兩個(gè)問題還有一些補(bǔ)充問題的簡(jiǎn)單思考：

1.Header與空閑空間相剝離，Header中包含一個(gè)指向其空閑空間的指針

　　這樣做未必不可，相應(yīng)地算法需要改動(dòng)。同時(shí)，由于Header和空閑空間不再相鄰，sbrk()獲得的空間也應(yīng)該包含Header的部分，內(nèi)存的分布可能會(huì)更加瑣碎。當(dāng)然，這也可能帶來好處，即用其他數(shù)據(jù)結(jié)構(gòu)對(duì)鏈表進(jìn)行管理，比如按大小進(jìn)行hash，這樣查找起來更快。

2.關(guān)于sbrk()

　　sbrk()也是庫(kù)函數(shù)，它能使堆往棧的方向增長(zhǎng)，具體可以參考：brk(), sbrk() 用法詳解。

3.可以改進(jìn)的方

　　空閑空間的尋找是線性的，查找過程在內(nèi)存分配中可以看作是循環(huán)首次適應(yīng)算法，在某些情況下可能很慢；如果再建立一個(gè)數(shù)據(jù)結(jié)構(gòu)，如hash表，對(duì)不同大小的空間進(jìn)行索引，肯定可以加快查找本身，并且能實(shí)現(xiàn)一些算法，比如最佳匹配。但查找加快的代價(jià)是，修改這個(gè)索引會(huì)占用額外的時(shí)間，這是需要權(quán)衡的。

　　morecore()中的最小分配空間是宏定義，在實(shí)際使用中完全可以作為參數(shù)傳遞，根據(jù)需要設(shè)定最小分配下限。

您可能感興趣的文章: