对于c语言存储分配程序(malloc函数)实现的理解

内容主要出自《The C Programming Language》一书,不得不说这是一本程序员必读的书,我大二读了前面几章就扔到一边了,直到最近才又拿起来再读,找不到言语来形容我现在后悔的心情....读的时候发现书中有好几处写错的地方,可能是我的版本比较旧的原因吧,我在文章中都改了过来。

 先贴上所有的代码然后再根据书中的解释细致的分析,建议最好把代码手敲一遍,理解会更深刻。

 1 typedef long Align;/*用于保证最受限类型可以对齐*/
 2 union header{               /*头部*/
 3     struct{
 4         union header *ptr;  /*下一个空闲块的指针*/
 5         unsigned size;      /*块的大小,空闲块被要求是头部长度的整倍数,size就是这个倍数,所以空闲块的实际长度是size*sizeof(header)*/
 6     }s;
 7     Align x;
 8 };
 9 typedef union header Header;
10 static Header base;             /*空的空闲块链表*/
11 static Header *freep = NULL;    /*指向空闲块链表的当前节点*/
12 
13 
14 Header *morecore(unsigned); /*当malloc函数无法分配合适的存储空间时,morecore方法会向系统申请更多存储空间*/
15 void free(void *);/*free方法用于释放malloc函数分配的内存空间,并将适当的空闲块合并成大块,减少碎片*/
16 
17 void *malloc(unsigned nbytes)
18 {
19     Header *p,*prevp;
20     unsigned nunits;
21     nunits = (nbytes+sizeof(Header)-1)/sizeof(header)+1;/*实际长度要比申请的大1,因为要考虑头部*/
22     if((prevp = freep)== NULL){ /*还没有初始化空闲块*/
23         base.s.ptr = freep = prevp = &base;
24         base.s.size = 0;
25     }
26     for(p = prevp->s.ptr;;prevp = p,p=p->s.ptr){
27         if (p->s.size >= nunits) {/*该块足够大*/
28             if (p->s.size == nunits) {/*大小正好*/
29                 prevp->s.ptr = p->s.ptr;
30             }else{ /*当大于时,将尾部的足够大的块返回*/
31                 p->s.size -= nunits;
32                 p += p->s.size;
33                 p->s.size = nunits;
34             }
35             freep = prevp;
36             return (void *)(p+1);
37         }
38         if (p==freep) {
39             if ((p = morecore(nunits)) == NULL) {
40                 return NULL;
41             }
42         }
43     }
44 }
45 
46 #define NALLOC 1024
47 Header* morecore(unsigned nu)
48 {
49     char *cp,*sbrk(int);
50     Header *up;
51     if (nu<NALLOC) {
52         nu = NALLOC;
53     }
54     cp = sbrk(nu*sizeof(Header));
55     if (cp == (char*)-1) {
56         return NULL;
57     }
58     up = (Header*)cp;
59     up->s.size = nu;
60     free((void*)(up+1));
61     return freep;
62 }
63 
64 void free(void *ap)
65 {
66     Header *bp,*p;
67     bp = (Header*)ap -1;/*bp是要被释放内存的头部的指针*/
68     for (p = freep; !(bp>p&&bp<p->s.ptr); p = p->s.ptr) {/*从当前空闲块开始寻找bp是否位于p和p的下一个块空闲块之间*/
69         if (p>=p->s.ptr&&(bp>p||bp<p->s.ptr)) {/*当p>=p->s.ptr时,p位于链表的尾部,p->s.ptr位于链表的头部*/
70             break;
71         }
72     }
73     if (bp+bp->s.size == p->s.ptr) {/*如果bp与后面的块相邻就合并了两个块*/
74         bp->s.size += p->s.ptr->s.size;
75     }else{
76         bp->s.ptr = p->s.ptr;
77     }
78     if (p+p->s.size == bp) {/*如果bp与前面的空闲块相邻就合并两个块*/
79         p->s.size += bp->s.size;
80         p->s.ptr = bp->s.ptr;
81     }else{
82         p->s.ptr = bp;
83     }
84     freep = p;
85 }

 malloc函数管理着一些空闲存储空间,这些空间不一定是连续的,而是以空闲块链表的方式组织的,每个块包含一个长度、一个指向下一个空闲块的指针以及一个指向自身存储空间的指针。这些空闲块按照存储地址的升序组织,最后一块指向第一块。

 当调用malloc函数申请空间时,malloc将扫描空闲块链表,直到找到一个足够大的块为止。该算法成为“首次适应”,与之相对的算法是“最佳适应”,它寻找满足条件的最小块。如果该块恰好与请求的大小相符合,则将它从链表中移走并返回给用户。如果该块太大,则将它分成两部分:大小合适的块返回给用户,剩下的部分留在空闲块链表中。如果找不到一个足够大的块,则向操作系统申请一个大块并加入到空闲块链表中。

释放过程也是首先搜索空闲块链表,以找到可以插入被释放块的合适位置。如果与被释放块相邻的一边是一个空闲块,则将这两个块合成一个更大的块,这样存储空间不会有太多的碎片。因为空闲块链表是以地址的递增顺序链接在一起的,所以很容易判断相邻的块是否空闲。malloc函数返回的存储空间要满足将要保存的对象的对齐要求。虽然及其类型各异,但是,每个特定的机器都一个最受限的类型:如果最受限的类型可以存储在某个特定的地址中,则其它所有的类型也可以存放在此地址中。在某些机器中,最受限的类型是double类型;而在另外一些机器中,最受限的类型是int或long类型。

位于块开始处的控制信息被称为“头部”,为了简化块的对齐,所有块的大小都必须是头部大小的整数倍,且头部已正确地对齐。这是通过一个联合实现的,该联合包含所需的头部结构以及一个对齐要求最受限的类型的实例,在下面这段程序中,我们假定long类型为最受限的类型:

typedef long Align;/*用于保证最受限类型可以对齐*/
union header{               /*头部*/
    struct{
        union header *ptr;  /*下一个空闲块的指针*/
        unsigned size;      /*块的大小,空闲块被要求是头部长度的整倍数,size就是这个倍数,所以空闲块的实际长度是size*sizeof(header)*/
    }s;
    Align x;
};
typedef union header Header;

在该联合中,Align字段永远不会被使用,它仅仅用于强制每个头部在最坏的情况下满足对齐要求。在malloc函数中,请求的长度(以字符为单位)将被舍入,以保证它是头部大小的整数倍。实际分配的块将多包含一个单元,用于头部本身。实际分配的块的大小将被记录在头部的size字段中。malloc函数返回的指针将指向空闲空间,而不是头部的块。用户可对获得的存储空间进行任何操作,但是,如果在分配的存储空间之外写入数据,则可能会破坏块链表。

 

其中的size字段是必须的,因为由malloc函数控制的块不一定是连续的,这样就不可能通过指针算术运算计算其大小。

 

static Header base;             /*空的空闲块链表*/
static Header *freep = NULL;    /*指向空闲块链表的当前节点*/

Header *morecore(unsigned); /*当malloc函数无法分配合适的存储空间时,morecore方法会向系统申请更多存储空间*/
void free(void *);/*free方法用于释放malloc函数分配的内存空间,并将适当的空闲块合并成大块,减少碎片*/

void *malloc(unsigned nbytes)
{
    Header *p,*prevp;
    unsigned nunits;
    nunits = (nbytes+sizeof(Header)-1)/sizeof(header)+1;/*实际长度要比申请的大1,因为要考虑头部*/
    if((prevp = freep)== NULL){ /*还没有初始化空闲块*/
        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) {/*该块足够大*/
            if (p->s.size == nunits) {/*大小正好*/
                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) {
            if ((p = morecore(nunits)) == NULL) {
                return NULL;
            }
        }
    }
}

base表示空闲块链表的头部。第一次调用malloc函数时,freep为NULL,系统将创建一个退化的空闲块链表,它只包含一个大小为0的块,且该块指向它自己。任何情况下,当请求空闲空间时,都将搜索空闲块链表。搜索从上一次找到空闲块的地方(freep)开始。该策略可以保证链表是均匀的。如果找到的块太大,则将其尾部返回给用户,这样,初始块的头部只需要修改size字段即可。在任何情况下,返回给用户的指针都指向块内的空闲存储空间,即比指向头部的指针大一个单元。

#define NALLOC 1024
Header* morecore(unsigned nu)
{
    char *cp,*sbrk(int);
    Header *up;
    if (nu<NALLOC) {
        nu = NALLOC;
    }
    cp = sbrk(nu*sizeof(Header));
    if (cp == (char*)-1) {
        return NULL;
    }
    up = (Header*)cp;
    up->s.size = nu;
    free((void*)(up+1));
    return freep;
}

函数morecore用于向操作系统请求存储空间,其实现细节因系统的不同而不同。因为向系统请求存储空间是一个开销很大的操作,因此,我们不希望每次调用malloc函数时都执行该操作,基于这个考虑,morecore函数请求至少NALLOC个单元。这个较大的块将根据需要分成较小的块。在设置完size字段之后,morecore函数调用free函数把多余的存储空间插入到空闲区域中。UNIX系统调用sbrk(n)返回一个指针,该指针指向n个字节的存储空间。如果没有空闲空间,尽管返回NULL可能更好一些,但sbrk调用返回-1.必须将-1强制转换为char*类型,以便与返回值进行比较。而且,强制类型转换使得该函数不会受不同机器中指针表示的不同的影响。但是,这里仍然假定,由sbrk调用返回的指向不同块的多个指针之间可以进行有意义的比较。ANSI标准并没有保证这一点,它只允许指向同一个数组的指针间的比较。因此,只有在一般指针间的比较操作有意义的机器上,该版本的malloc函数才能够移植。

void free(void *ap)
{
    Header *bp,*p;
    bp = (Header*)ap -1;/*bp是要被释放内存的头部的指针*/
    for (p = freep; !(bp>p&&bp<p->s.ptr); p = p->s.ptr) {/*从当前空闲块开始寻找bp是否位于p和p的下一个块空闲块之间*/
        if (p>=p->s.ptr&&(bp>p||bp<p->s.ptr)) {/*当p>=p->s.ptr时,p位于链表的尾部,p->s.ptr位于链表的头部*/
            break;
        }
    }
    if (bp+bp->s.size == p->s.ptr) {/*如果bp与后面的块相邻就合并了两个块*/
        bp->s.size += p->s.ptr->s.size;
    }else{
        bp->s.ptr = p->s.ptr;
    }
    if (p+p->s.size == bp) {/*如果bp与前面的空闲块相邻就合并两个块*/
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    }else{
        p->s.ptr = bp;
    }
    freep = p;
}

我们最后来看一下free函数。它从freep指向的地址开始,逐个扫描空闲块链表,寻找可以插入空闲块的地方。该位置可能在两个空闲块之间,也可能在链表的末尾。在任何一种情况下,如果被释放的块与另一空闲块相邻,则将这两个块合并起来。合并两个块的操作很简单,只需要设置指针指向正确的位置,并设置正确的块大小就可以了。虽然存储分配从本质上是与机器相关的,但是,以上的代码说明了如何控制与具体机器相关的部分,并将这部分程序控制到最少量。typedef和union的使用解决了地址的对齐(假定sbrk返回的是合适的指针)问题。类型的强制转换使得指针的转换是显式进行的,这样做甚至可以处理设计不够好的系统接口问题。虽然这里所讲的内容只涉及到存储分配,但是,这种通用方法也适用于其它情况。

posted @ 2017-09-14 11:29 子衿时代 阅读(...) 评论(...) 编辑 收藏