malloc并不是从一个编译时就确定的固定大小的数组中分配空间，而是在需要的时向操作系统申请空间。因为程序中的某些地方可能不通过malloc调用申请空间（通过其它方式申请空间），因此，malloc管理的空间不一定是连续的。这样空闲存储空间以空闲块链表的方式组织，每个块包含一个长度、一个指向下一块的指针以及一个指向自身存储空间的指针。
当有申请请求时，malloc将扫描空闲块链表，直到找到一个足够大的块为止。该算法称为“首次适应”（first fit）；与之相对应的算法是“最佳适应”（best fit），它寻找满足条件的最小块。如果该块恰好与请求的大小相符合，则将它从链表中移走并返回给用户。如果该块太大，则将它分成两部分；大小合适的块返回给用户，剩下的部分留在空闲块链表中。如果找不到一个足够大的块，则向操作系统申请一个大块并加入到空闲块链表中。
malloc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| typedef long Align; /*按照long类型的边界对齐*/
union header { /*块的头部*/
struct {
union header *ptr; /*空闲块链表的下一块*/
unsigned size; /*本块的大小*/
}s;
Align x; /*强制块对齐*/
};
typedef union header Header;
static Header base; /*从空链表开始*/
static Header *freep = NULL /*空闲链表的初始指针*/
/*malloc函数:通用存储分配函数*/
void *malloc( unsigned nbytes)
{
Header *p, *prevp;
Header *morecore(unsigned);
unsigned nunits;
nunits = (nbytes + sizeof(Header)-1)/sizeof(Header) + 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; /*没有剩余的存储空间*/
}
}
|
函数morecore用于向操作系统请求存储空间。在设置完size字段后，morecore函数调用free函数把多余的存储空间插入到空闲区域中。
morecore
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #define NALLOC 1024
/*morecore函数:向系统申请更多的存储空间*/
static Header *morecore(unsigned nu)
{
char *cp, *sbrk(int);
Header *up;
cp = sbrk(nu*sizeof(Header));
if ( cp == (char *) - 1) /*没有空间*/
return NULL;
up = (Header *)cp;
up->s.size = nu;
free((void*)(up+1));
return freep;
}
|
free函数从freep指向的地址开始，逐个扫描空闲块链表，寻找可以插入空闲块的地方。该位置可能在两个空闲块之间，也可能在链表的末尾。在任何一种情况下，如果被释放的块与另一空闲块相邻，则将这两个块合并起来。合并两个块的操作很简单，只需要设置指针指向正确的位置，并设置正确的块大小就可以了。
free
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| /*free函数:将块ap放入空闲块链表中*/
void free(void *ap)
{
Header *bp, *p;
bp = (Header *)ap -1; /*指向块头*/
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; /*被释放的块在链表的开头或末尾*/
if( bp + bp->s.size == p->s.ptr) /*与上一相邻块合并*/
{
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) /*与下一相邻块合并*/
{
p->s.size += bp->s.size;
p->s.ptr = bp->s.ptr;
}
else
p->s.ptr = bp;
freep = p;
}
|
typedef和union的使用解决了地址对齐（假定sbrk返回的是合适的指针)问题