基于malloc與free函數的實作代碼及分析

　　在研究K&R第八章第五節的實作之前，不妨先看看其第五章第四節的alloc/afree實作，雖然這段代碼主要目的是展示位址運算。

複制代碼

alloc實作

#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;

}

這種簡單實作的缺點：

　　　　1.作為代表記憶體資源的allocbuf，其實是預先配置設定好的，可能存在浪費。

　　　　2.配置設定和釋放的順序類似于棧，即“後進先出”，釋放時如果不按順序會造成異常。

　　這個實作雖然比較簡陋，但是依然提供了一個思路。如果能把這兩個缺點消除，就能夠實作比較理想的malloc/free。

需要使用指針把同類的記憶體空間連接配接起來形成連結清單，這樣就可以處理位址不連續的一系列記憶體空間。但是為什麼隻連接配接了空閑空間而不連接配接使用中的空間？這麼問可能出于在對圖中二者類比時的直覺而沒有經過思考，這很簡單，因為沒有必要。前者互相連結是為了能夠在記憶體配置設定時周遊所有空閑空間，并且在使用free()回收已使用空間時進行重新插入。而對于使用中的空間，由于我們在配置設定空間時已經知道它們的位址了，回收時可以直接告訴free()，并不用像malloc()時進行周遊。

作為待配置設定的記憶體區域，大小是不定的，如果把它聲明為struct的成員變量顯然不妥；如果聲明為一個指向某個其他的區域的指針，這似乎又和上面的直覺表示不相符合。（當然，這麼做也是可以實作的，它看上去是介于上圖的兩者之間，把管理結構和實際配置設定的空間相剝離，在文末我會專門的讨論一下這種實作方法）是以，這裡仍然把控制結構和空閑空間相分開，但保持它們在記憶體位址中相鄰，形成下圖的形式，而正由這個特點，我們可以利用對控制結構指針的指針運算來定位對應的記憶體區域：

　　

　　對應地，把控制資訊定義為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;

使用union而不是直接使用struct的原因是為了位址對齊。這裡是long對齊，union的x永遠不會使用。

　　這樣，malloc的主要工作就是對這些Header和其後的記憶體塊的管理。

複制代碼

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大小的整數倍，并且多出一個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()第一次調用時建立一個退化連結清單base，隻有一個大小是0的空間，并指向它自己。freep用于辨別空閑連結清單的某個元素，每次查找時可能發生變化；中間的查找和配置設定過程是基本的連結清單操作，在空閑連結清單中不存在合适大小的空閑空間時調用morecore()獲得更多記憶體空間；最後的傳回值是空閑空間的首位址，即Header之後的位址，這個接口與庫函數一緻。

複制代碼

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()從系統申請更多的可用空間，并加入。由于調用了sbrk()，

系統開銷比較大，為避免morecore()本身的調用次數，設定了一個NALLOC，如果每次申請的空間小于NALLOC，就申請NALLOC大小的空間，使得後續malloc()不必每次都需要調用morecore()。

對于sbrk()，在後面會有介紹。

malloc()調用了morecore()，morecore()又調用了free()！第一次看到這裡時可能會覺得不可思議，因為按照慣性思維，malloc()和free()似乎應該是互相分開的，各司其職啊？但請再思考一下，free()是把空閑連結清單進行擴充，而malloc()在空閑連結清單不足時，從系統申請到更多記憶體空間後，也要先把它們轉化成空閑連結清單的一部分，再進行利用。這樣，malloc()調用free()完成後面的工作也是順理成章了。根據這個思想，後面是free()的實作。在此之前，還有幾個morecore()自身的細節：

1.如果系統也沒有空間可以配置設定，sbrk()傳回-1。cp是char *類型，在有的機器上char無符号，這裡需要一次強制類型轉換。

2.morecore()調用的傳回值看上去比較奇怪，别擔心，freep會在free()中修改的。使用這個傳回值也是為了在malloc()裡的判斷、p = freep的再次指派的語句能夠緊湊。

複制代碼

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對應的bp與空閑連結清單的相對位置，找到它的的最近的上一個和下一個空閑空間，或是當它在整個空閑空間的前面或後面時找到空閑連結清單的首尾元素。注意，由于malloc()的配置設定方式和free()的回收時的合并方式（下文馬上要提到），可以保證整個空閑空間的連結清單總是從低位址逐個升高，在最高位址的空閑空間回指向低位址第一個空閑空間。

兩個if并列可以使得bp可以同時與高位址和低位址空閑空間結合（如果都相鄰），或者進行二者之一的合并，或者不合并。

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

　　第一次審視源碼，會發現很多實作可能原先并沒有想到：Header的結構和對齊填充、空間的取整、連結清單的操作和初始化（邊界情況）、malloc()對free()的調用、由malloc()和free()暗中保證的連結清單位址有序等等，确實很值得玩味。另外再附上前文中提到的兩個問題還有一些補充問題的簡單思考：

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

　　這樣做未必不可，相應地算法需要改動。同時，由于Header和空閑空間不再相鄰，sbrk()獲得的空間也應該包含Header的部分，記憶體的分布可能會更加瑣碎。當然，這也可能帶來好處，即用其他資料結構對連結清單進行管理，比如按大小進行hash，這樣查找起來更快。

2.關于sbrk()

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