malloc_lab

Posted on
Words count in article: 1.9k | Reading time ≈ 8

malloc lab

隐式空闲链表(书本)

基本设计

在博客CSAPP动态内存分配 中，我们已经详细介绍了隐式空闲链表的分配原理了。那么我们这次就来手动实现一个简单的分配器

首先我们来介绍一下分配器需要输出给应用程序的三个函数：

extern int mm_init(void) 这个函数的作用是初始化分配器，如果成功，那么就返回0；否则就返回-1

extern void *mm_malloc(size_t size) 这个函数就是分配空间

extern void mm_free(void *ptr) 这个函数是释放空间

我们要申请的块格式如下，具有头部和尾部，最小的块大小为16字节：

整一个隐式空闲链表如下图所示：

第一个字是一个双字边界对齐的不使用的填充字。填充后面紧跟着一个特殊的序言块。这是一个8字节的已分配块，只由头部和尾部组成。序言块是在初始化的时候创建的，并且是永不释放的。在序言块的后面紧跟着的是零个或者多个由mallock或者free调用创建的普通块。在结尾处，是一个大小为0的已分配块，只由一个头部组成。

序言块和结尾块是一种消除合并时边界条件的技巧。

宏介绍

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
#define ALIGNMENT 8//首先是ALIGNMENT，也就是我们要8字节对齐，向8的倍数舍入。
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
//这是为size找到比它大又是最小的8的倍数

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

#define WSIZE 4				//单字长度
#define DSIZE 8             /*Double word size*/
#define CHUNKSIZE (1 << 12) /*the page size in bytes is 4K*/

#define MAX(x, y) ((x) > (y) ? (x) : (y))//两个数中取最大值

#define PACK(size, alloc) ((size) | (alloc)) //将分配大小和标记位合并

#define GET(p) (*(unsigned int *)(p)) //读取和返回参数p引用的字
#define PUT(p, val) (*(unsigned int *)(p) = (val))//将val存放在p指向的字中

#define GET_SIZE(p) (GET(p) & ~0x7)// 从地址p处的头部或者脚部返回大小
#define GET_ALLOC(p) (GET(p) & 0x1)// 返回已分配位

#define HDRP(bp) ((char *)(bp)-WSIZE)//给定块指针，返回它的头部指针
//此bp是从有效载荷开始的，因此指向块的头部，得减去一个4字节
#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)))
//指向前面的块的块指针

mm_init

mm_init函数从内存系统得到4个字，并将其初始化，创建一个空的空闲链表。然后它调用extend_heap函数。这个函数将堆扩展CHUNKSIZE 字节，并且创建初始的空闲块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int mm_init(void)
{
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
    {
        return -1;
    }
    PUT(heap_listp, 0); //哨头
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1));
    //序言头块，在此地址上写上块大小的数据
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1));
    //序言尾块，在此地址上写上块大小的数据
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); //结束块
    heap_listp += (2 * WSIZE);
    // 为我们的链表创造CHUNKSIZE的空间
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
        return -1;
    return 0;
}

现在，分配器已经初始化了，并且准备好接受来自应用的分配和释放请求

extend_heap

这个函数当堆被初始化的时候或者当mm_malloc 不能找到一个合适的分配块的时候。为了保持对齐，extend_heap会将其请求大小向上舍入为最接近的2字(8字节)的倍数，然后向内存系统请求额外的堆空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;//向上舍入
    if ((long)(bp = mem_sbrk(size)) == (void *)-1)//向内存要空间
        return NULL;

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));

    return coalesce(bp);
}

mm_free 函数

1
2
3
4
5
6
7
8
9
10
void mm_free(void *bp)
{
    if (bp == 0)
        return;
    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

free函数可以释放一个以前分配的块，这个函数释放所请求的块bp,然后我们将其与邻接的空闲块合并起来

coalesce函数

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
30
31
32
33
34

static void *coalesce(void *bp)
{
    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));//首先我们获得前后块的分配位
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));
	//如果前面和后面都是已分配的，那么就直接返回bp
    if (prev_alloc && next_alloc)
        return bp;
    //如果前面的块已分配，后面的块没有分配，那么Size就等于当前块加上后面的块的大小
    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));
    }
    //如果后面的块已分配，前面的块没分配，那么size就等于当前块加上前面的块的大小
    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);
    }
    //如果都是空的，那么size就等于前后中三个块的大小，然后修改指针
    else
    {
        size += GET_SIZE(FTRP(NEXT_BLKP(bp))) + GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    return bp;
}

mm_malloc函数

应用会通过调用mm_malloc函数来向内存请求大小为size字节的块。在检查完请求的真假之后，分配器必须调整请求快的大小，从而为头部和脚部留有空间并满足双字对齐的要求。

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_malloc(size_t size)
{
    size_t asize;
    size_t extendsize;
    char *bp;
    if (size == 0)
        return NULL;

    if (size <= DSIZE)//强行限制了最小块大小为16字节；8字节用来满足对齐要求，8字节用来放头部尾部
        asize = 2 * (DSIZE);
    else//向上舍入到最接近8的整数倍
        asize = (DSIZE) * ((size + (DSIZE) + (DSIZE - 1)) / (DSIZE));

    if ((bp = find_fit(asize)) != NULL)//找到合适的block存放
    {
        place(bp, asize);
        return bp;
    }
    extendsize = MAX(asize, CHUNKSIZE);//如果没有合适的，那么我们就要extend_size了
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
    {
        return NULL;
    }
    place(bp, asize);
    return bp;
}

find_fit函数

这里，我们采取的方法是first_fit,也就是找到第一个符合条件的block来放置。

1
2
3
4
5
6
7
8
9
10
static void *find_fit(size_t size)
{
    void *bp;
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
    {
        if (!GET_ALLOC(HDRP(bp)) && (size <= GET_SIZE(HDRP(bp))))
            return bp;
    }
    return NULL;
}

最佳适配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void *best_fit(size_t asize){
	void *bp = heap_listp;
	size_t size;
	void *best = NULL;
	size_t min_size = 0;
	while((size = GET_SIZE(HDRP(bp))) != 0){
		if(size >= asize && !GET_ALLOC(HDRP(bp)) && (min_size == 0 || min_size>size)){	
            //记录最小的合适的空闲块
			min_size = size;
			best = bp;
		}
		bp = NEXT_BLKP(bp);
	}
	return best;
}

place函数

place函数就是将此适配的块的头部和尾部进行修改，如果剩下的尺寸超过16，则将其重新加入空闲块中，避免内部碎片;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));
    if ((csize - asize) >= (2 * DSIZE))
    { 
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize - asize, 0));
        PUT(FTRP(bp), PACK(csize - asize, 0));
    }
    else
    {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

mm_realloc函数

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
27
28
29
30
31
32
33
34
35
36
37
void *mm_realloc(void *ptr, size_t size)
{
    size_t oldsize;
    void *newptr;

    /* If size == 0 then this is just free, and we return NULL. */
    if (size == 0)
    {
        mm_free(ptr);
        return 0;
    }

    /* If oldptr is NULL, then this is just malloc. */
    if (ptr == NULL)
    {
        return mm_malloc(size);
    }

    newptr = mm_malloc(size);

    /* If realloc() fails the original block is left untouched  */
    if (!newptr)
    {
        return 0;
    }

    /* Copy the old data. */
    oldsize = GET_SIZE(HDRP(ptr));
    if (size < oldsize)
        oldsize = size;
    memcpy(newptr, ptr, oldsize);

    /* Free the old block. */
    mm_free(ptr);

    return newptr;
}
-------------本文结束，感谢您的阅读-------------