0x00 Overview

可以看一下要求：http://csapp.cs.cmu.edu/3e/malloclab.pdf

0x01 组织模式

隐式空闲链表

隐式空闲链表的结构：

img

隐式空闲链表利用空闲块头部的标志位将空闲块间接的连接起来。

遍历整个堆时，遇到已经分配块自动跳过，根据空闲部头部的size来寻找空闲块。

0x02 隐式空闲链表

mm_init

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int mm_init(void)
{
    if((heap_listp=mem_sbrk(4*WSIZE))==(void*)-1)
        return -1;
    // topchunk 16字节 heap_listp[3]
    PUT(heap_listp,0);
    // heap_listp[0] = 0
    PUT(heap_listp+(1*WSIZE),PACK(DSIZE,1));
    // heap_listp[1] = 1001
    PUT(heap_listp+(2*WSIZE),PACK(DSIZE,1));
    // heap_listp[2] = 1001
    PUT(heap_listp+(3*WSIZE),PACK(0,1));
    // heap_listp[3] = 0001
    heap_listp+=(2*WSIZE);
    // 把堆指针指向heap_listp[2]
    if(extend_heap(CHUNKSIZE/WSIZE)==NULL)
        return -1;
    return 0;
}

mem_sbrk函数，有一点要注意一下，mem_brk永远指向堆的最后一个字节。

1
2
3
4
5
6
7
8
9
10
11
12
void *mem_sbrk(int incr) 
{
    char *old_brk = mem_brk;

    if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) {
	errno = ENOMEM;
	fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n");
	return (void *)-1;
    }
    mem_brk += incr;
    return (void *)old_brk;
}

extend_heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static void *extend_heap(size_t words)
{
    // extend_heap只会在两种情况下被调用
    // 1.当堆被初始化时
    // 2.当mm_malloc不能找到一个合适的块时
    char* bp;
    size_t size;
    size = (words%2)?(words+1)*WSIZE : words * WSIZE;
    // 必须是偶数，保持8字节对齐
    if((long)(bp=mem_sbrk(size))==-1)
        return NULL;
// #define HDRP(bp) ((char*)(bp)-WSIZE)
// #define FTRP(bp) ((char*)(bp)+GET_SIZE(HDRP(bp))-DSIZE)
    PUT(HDRP(bp),PACK(size,0));
    PUT(FTRP(bp),PACK(size,0));
// #define NEXT_BLKP(bp) ((char*)(bp)+GET_SIZE(((char*)(bp)-WSIZE)))
    PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));
    return coalesce(bp);
}

当堆被初始化时调用extend_heap函数时的情形

  1. 调用完mem_sbrk

  1. 运行完 PUT(HDRP(bp),PACK(size,0));将结尾块变成起始块，赋值上size和alloc。

  2. PUT(FTRP(bp),PACK(size,0));将size-8的位置设置上footer，因为把header和footer都算进size里了。

  3. PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));将最后一个字变成结尾块

宏定义

如果前面的看懂了，那就可以理解所有的宏定义了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12)
#define MAX(x,y) ((x)>(y)?(x):(y))
#define PACK(size,alloc) ((size)|(alloc))
// 在地址处读写一个数据
#define GET(p) (*(unsigned int*)(p))
#define PUT(p,val) (*(unsigned int*)(p)=(val))
// 在地址处获取size和alloc位
// 因为最少也是8字节，所以~0x7
#define GET_SIZE(p) (GET(p)&~0x7)
#define GET_ALLOC(p) (GET(p)&0x1)
// 获取堆的头部和尾部
#define HDRP(bp) ((char*)(bp)-WSIZE)
#define FTRP(bp) ((char*)(bp)+GET_SIZE(HDRP(bp))-DSIZE)
// 下个堆和上个堆的地址
#define NEXT_BLKP(bp) ((char*)(bp)+GET_SIZE(((char*)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char*)(bp)-GET_SIZE(((char*)(bp)-DSIZE)))

coalesce

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
static void *coalesce(void *bp)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); // 获得上一个块的alloc
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); // 获得下一个块的alloc

    size_t size=GET_SIZE(HDRP(bp)); // 获得当前块的size
    if(prev_alloc&&next_alloc){
        // mm_init->extend_heap 就会直接return
        return bp;
    }
    else if (prev_alloc&&!next_alloc){
        size+=GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp),PACK(size,0));
        PUT(FTRP(bp),PACK(size,0));
    }
    else if (!prev_alloc && next_alloc) {
        size+=GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp),PACK(size,0));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        bp=PREV_BLKP(bp);
    }
    else{
        size+=GET_SIZE(HDRP(PREV_BLKP(bp)))+GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
        PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
        bp=PREV_BLKP(bp);
    }
    return bp;
}

image-20220220235845889

mm_free

1
2
3
4
5
6
7
8
9
void mm_free(void *bp)
{
    size_t size=GET_SIZE(HDRP(bp));
    PUT(HDRP(bp),PACK(size,0));
    PUT(FTRP(bp),PACK(size,0));
    // header和footer的alloc设置为0
    coalesce(bp);
    // free之后立即合并
}

mm_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
void* mm_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    char *bp;
    if(size==0)
        return NULL;
    if(size<=DSIZE)
        asize=2*DSIZE;
    // 最小分配16
    // 一是因为8字节对齐，二是因为header和footer
    else
        asize=DSIZE*((size+(DSIZE)+(DSIZE-1))/DSIZE);
    // 其中第一个DSIZE表示header+footer
    // 因为size肯定大于8，所以第二个DSIZE-1和size加起来肯定大于等于16，也就是分配两个以上的块
    
    if((bp=find_fit(asize)) != NULL){
    // 首次匹配
        place(bp,asize);
        return bp;
    }
    // 如果没有匹配到适合的chunk,最少分配chunksize个字节
    extendsize=MAX(asize,CHUNKSIZE);
    if((bp=extend_heap(extendsize/WSIZE))==NULL)
        return NULL;
    place(bp,asize);
    return bp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static void *find_fit(size_t asize) {
	void *bp = heap_listp;
	size_t size;
	while((size = GET_SIZE(HDRP(bp))) != 0){	//遍历全部块
		if(size >= asize && !GET_ALLOC(HDRP(bp)))	//寻找大小大于asize的空闲块
			return bp;
		bp = NEXT_BLKP(bp);
	}
	return NULL;
}
static void place(void *bp, size_t asize) {
	size_t remain_size;
	remain_size = GET_SIZE(HDRP(bp)) - asize;	//计算空闲块去掉asize后的剩余空间
	if(remain_size >= DSIZE){	//如果剩余空间满足最小块大小，就将其作为一个新的空闲块
		PUT(HDRP(bp), PACK(asize, 1));
		PUT(FTRP(bp), PACK(asize, 1));
		PUT(HDRP(NEXT_BLKP(bp)), PACK(remain_size, 0));
		PUT(FTRP(NEXT_BLKP(bp)), PACK(remain_size, 0));
	}else{
		PUT(HDRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
		PUT(FTRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
	}
}

mm_realloc

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
void *mm_realloc(void *ptr, size_t size) {
    void *p;
    size_t copy_size;
    if (ptr == NULL) {
        p = mm_malloc(size);
        return p;
    }
    if (size == 0) {
        mm_free(ptr);
        return NULL;
    }

    copy_size = GET_SIZE(ptr-WSIZE);
    p = mm_malloc(size);
    if (!p) {
        return NULL;
    }

    if (size < copy_size)
        copy_size = size;

    memcpy(p, ptr, copy_size);
    mm_free(ptr);

    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void *find_fit(size_t asize) {
	void *bp = heap_listp;
	size_t size;
	while((size = GET_SIZE(HDRP(bp))) != 0){	//遍历全部块
		if(size >= asize && !GET_ALLOC(HDRP(bp)))	//寻找大小大于asize的空闲块
			return bp;
		bp = NEXT_BLKP(bp);
	}
	return NULL;
}
static void place(void *bp, size_t asize) {
	size_t remain_size;
	remain_size = GET_SIZE(HDRP(bp)) - asize;	//计算空闲块去掉asize后的剩余空间
	if(remain_size >= DSIZE){	//如果剩余空间满足最小块大小，就将其作为一个新的空闲块
		PUT(HDRP(bp), PACK(asize, 1));
		PUT(FTRP(bp), PACK(asize, 1));
		PUT(HDRP(NEXT_BLKP(bp)), PACK(remain_size, 0));
		PUT(FTRP(NEXT_BLKP(bp)), PACK(remain_size, 0));
	}else{
		PUT(HDRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
		PUT(FTRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
	}

}

看完别人写的思路其实差不多懂了，懒得再写了。直接啃源码去了。