本次实验的内容也比较清晰，只需要完成一个手写的 malloc 动态内存分配器即可。

书上第 99 章第 99 节介绍了这样的分配器的实现方法。

实验要求

本次实验提供了基本的框架，需要完成下面几个函数：

1
2
3
4
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);

分别是，分配器的初始化、分配内存、释放内存、重新分配内存等操作。

mdriver 程序将对分配器的空间利用率和吞吐量进行评判，如果 UU 代表最终的空间利用率，TT 代表吞吐量，那么我们的得分 PP 就是它们的加权和：

P=wU+(1−w)min⁡(1,TTlibc)P = wU + (1 -w)\min\left(1, \frac{T}{T_{libc}}\right)

其中，ww 为加权系数，默认为 0.60.6。

组织结构和放置策略介绍

影响分配器的空间利用率和吞吐量最重要的因素就是空闲块的组织结构和放置策略。

具体地，一共有下面几种组织结构：

  • 隐式空闲链表（Implicit Free List）：把所有的块连接起来，而且是通过头部中的大小字段隐含地连接着的，每次都需要遍历所有块来找到合适的空闲块。
  • 显式空闲链表（Explicit Free Lists）：在空闲块中增加两个指针，分别指向链表中前一块和后一块，这样就不需要遍历所有块，只需要遍历空闲块。
  • 分离的空闲链表（Segregated Free Lists）：维护多个空闲链表，其中每个链表中的块有大致相等的大小。分为三种：
    • 简单分离存储（simple segregated storage）：每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小，从不合并与分离。
    • 分离适配（Segregated Fit）：分配器维护着一个空闲链表的数组。每个空闲链表是和一个大小类相关联的，并且被组织成某种类型的显式或隐式链表。每个链表包含潜在的大小不同的块， 这些块的大小是大小类的成员。
    • 伙件系统（buddy system）：分离适配的一种特例，其中每个大小类都是 22 的幂。

其中，C 标准库的 malloc 使用的就是分离适配的方法，在本实验中，为了对标 malloc，我们也将使用这种方法。

常见的放置策略有首次适配（first fit）、下一次适配（next fit）和最佳适配（best fit）：

  • 首次适配：从头开始搜素空闲链表，选择第 一个合适的空闲块。
  • 下一次适配：和首次适配很相似，只不过不是从链表的起始处开始每次搜索，而是从上一次查询结束的地方开始。
  • 最佳适配：检查每个空闲块，选择适合所需请求大小的最小空闲块。

一般来说，首次适配的优点是它趋向于将较大的空闲块保留在链表的后面，但是它趋向于在链表起始处留下小空闲块的 “碎片” ，这就增加了对较大块的搜索时间。最佳适配往往有用最好的空间利用率，但是需要完整遍历所有的空闲块。

在本实验中，我们将采用首次适配和最佳适配两种方式进行比较，选择最好的成绩。

事实上，即使使用首次适配，分离适配的空闲块组织结构已经带来了一部分最佳适配的特性。

宏定义

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
/* $begin mallocmacros */
/* Basic constants and macros */
#define WSIZE       4       /* Word and header/footer size (bytes) */ //line:vm:mm:beginconst
#define DSIZE       8       /* Double word size (bytes) */
#define CHUNKSIZE  (1<<12)  /* Extend heap by this amount (bytes) */  //line:vm:mm:endconst 

#define MAX(x, y) ((x) > (y)? (x) : (y))  

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc)  ((size) | (alloc)) //line:vm:mm:pack

/* Read and write a word at address p */
#define GET(p)       (*(unsigned int *)(p))            //line:vm:mm:get
#define PUT(p, val)  (*(unsigned int *)(p) = (val))    //line:vm:mm:put

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)  (GET(p) & ~0x7)                   //line:vm:mm:getsize
#define GET_ALLOC(p) (GET(p) & 0x1)                    //line:vm:mm:getalloc

/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)       ((char *)(bp) - WSIZE)                      //line:vm:mm:hdrp
#define FTRP(bp)       ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) //line:vm:mm:ftrp

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp)  ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) //line:vm:mm:nextblkp
#define PREV_BLKP(bp)  ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) //line:vm:mm:prevblkp

/* 分离适配链表相关 */
#define LIST_PRE(bp) (bp)
#define LIST_NEXT(bp) ((void *)((char *)bp + WSIZE))
#define LIST_HEAD(x) ((void *)((char *)(heap) + WSIZE * (x)))
#define GET_PRE(bp) ((void *)GET(LIST_PRE(bp)))
#define GET_NEXT(bp) ((void *)GET(LIST_NEXT(bp)))
#define GET_HEAD(x) ((void *)GET((char *)(heap) + WSIZE * (x)))
/* $end mallocmacros */

大致和书上使用的宏定义相同，不过最后有几个和分离适配的链表相关，LIST_PRE 和 LIST_NEXT 表示这个块上存储上一块和下一块的位置的指针，LIST_HEAD 表示第 ii 个大小类的头指针，GET_XXX 是这三个宏定义的解引用版本。

组织结构

image-20230908132615227

具体来说，分离适配的组织结构是上图的格式。

显然，因为头部和脚部，以及两个指针，一个空闲块至少有 44 个字。因此，我们一共分了 2020 个大小类，第 00 个大小类的大小为 1616，第 11 个大小类为 {17,…,32}\{17, \dots, 32\}，以此类推，第 i(1≤i<19)i(1 \leq i < 19) 个大小类为 {2i+3−1,…,2i+4}\{2^{i+3} - 1, \dots, 2^{i+4} \}。最后一个大小类为剩下的所有大小。

因此，我们可以写出一个确定大小类编号的函数：

1
2
3
4
5
6
int getlist(size_t size) {
    for (int i = 0; i < 19; ++i)
        if (size <= (1 << (i + 4)))
            return i;
    return 19;
}

初始化

初始化首先要申请 (20+4)×4(20 + 4) \times 4 个字节的空间，作为头指针、填充块、序言块和结尾块的位置。

最后再调用 extend_heap 函数申请一个 2122^{12} 大小的空闲块备用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int mm_init(void)
{
    if ((heap = mem_sbrk(24 * WSIZE)) == (void*)-1) return -1;
    for (int i = 0; i < 20; ++i)
        PUT(LIST_HEAD(i), NULL);
    
    PUT(LIST_HEAD(20), 0);
    PUT(LIST_HEAD(21), PACK(DSIZE, 1));
    PUT(LIST_HEAD(22), PACK(DSIZE, 1));
    PUT(LIST_HEAD(23), PACK(0, 1));

    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1;
    return 0;
}

extend_heap 的作用是将可用的堆空间扩展 CHUNKSIZE 个字节，这里是 2122^{12}。

1
2
3
4
5
6
7
8
9
10
11
void *extend_heap(size_t size) {
    size = ((size % 2) ? size + 1 : size) * WSIZE;
    void *p = mem_sbrk(size);
    if (p == (void *)-1) return NULL;

    PUT(HDRP(p), PACK(size, 0));
    PUT(FTRP(p), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(p)), PACK(0, 1));
    
    return coalesce(p);
}

其中，coalesce 函数是用来合并空闲块的，将在稍后给出。

注意到堆的空间是连续的，因此申请得到的地址的前一个字节就是原来的结尾块，这里我们将它覆盖成新的空闲块，将申请到的空间的最后一块作为新的结尾块。

这里不需要将空闲块加入链表，会在 coalesce 中合并完空闲块再加入。

链表相关

插入

因为我们要实现首次适配和最优适配的两种模式，因此在插入链表的过程会有些差异。

下面是首次适配的版本，首先我们找到所属的大小类，如果头指针指向为空，就直接接在头指针下面，否则取代掉头指针指向块的位置，作为新的头指针指向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ins(void *bp) {
    size_t size = GET_SIZE(HDRP(bp));
    int list = getlist(size);
    if (GET_HEAD(list) == NULL) {
        PUT(LIST_NEXT(bp), NULL);
        PUT(LIST_HEAD(list), bp);
        PUT(LIST_PRE(bp), NULL);
    } else {
        PUT(LIST_PRE(GET_HEAD(list)), bp);
        PUT(LIST_NEXT(bp), GET_HEAD(list));
        PUT(LIST_HEAD(list), bp);
        PUT(LIST_PRE(bp), NULL);
    }
}

下面是最优适配的版本。这里，我们确保了每个大小块中，所有空闲块都是按照大小排序的，头指针指向的为最小的块，越向后大小越大。

因此，在插入的时候，我们要在链表中找到合适的位置才能插入。

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
void ins(void *bp) {
    size_t size = GET_SIZE(HDRP(bp));
    int list = getlist(size);
    if (GET_HEAD(list) == NULL) {
        PUT(LIST_NEXT(bp), NULL);
        PUT(LIST_HEAD(list), bp);
        PUT(LIST_PRE(bp), NULL);
    } else {
        void *p, *q;
        for (p = GET_HEAD(list), q = NULL; p; q = p, p = GET_NEXT(p))
            if (GET_SIZE(HDRP(p)) >= size) {
                if (q == NULL) PUT(LIST_HEAD(list), bp);
                else PUT(LIST_NEXT(q), bp);
                PUT(LIST_NEXT(bp), p);
                PUT(LIST_PRE(p), bp);
                PUT(LIST_PRE(bp), q);
                return;
            }
        if (q == NULL) PUT(LIST_HEAD(list), bp);
        else PUT(LIST_NEXT(q), bp);
        PUT(LIST_NEXT(bp), p);
        if (p) PUT(LIST_PRE(p), bp);
        PUT(LIST_PRE(bp), q);
    }
}

删除

删除部分就简单了，不需要区分是哪种适配，只需要修改原本的前驱、后继的相关指针即可。

1
2
3
4
5
6
7
void del(void *bp) {
    size_t size = GET_SIZE(HDRP(bp));
    int list = getlist(size);
    if (GET_PRE(bp) == NULL) PUT(LIST_HEAD(list), GET_NEXT(bp));
    else PUT(LIST_NEXT(GET_PRE(bp)), GET_NEXT(bp));
    if (GET_NEXT(bp)) PUT(LIST_PRE(GET_NEXT(bp)), GET_PRE(bp));
}

合并与切割

合并

合并的过程是将连续的空闲块合成一个。因为我们采用了立即合并的思路，只要有新的空闲块诞生就立刻合并，保证了任意时刻空闲块都是不连续的。

具体的方法是判断新的空闲块的前一个块和后一个块是不是空闲的，将相邻的空闲块在原来的链表中删除，合并在一起，插入新的链表。

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 *coalesce(void *bp) {
    int prea = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    int nexta = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));
    
    if (prea && nexta) ;
    else if (prea && !nexta) {
        del(NEXT_BLKP(bp));
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    } else if (!prea && nexta) {
        del(PREV_BLKP(bp));
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        bp = PREV_BLKP(bp);
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    } else if (!prea && !nexta) {
        del(NEXT_BLKP(bp));
        del(PREV_BLKP(bp));
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
        bp = PREV_BLKP(bp);
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    ins(bp);
    return bp;
}

切割

分离就是在需要使用空闲块的时候，将一个空闲块切割成需要的已分配块，和新的空闲块。

因为空闲块的大小至少为 44，因此如果空闲块大小和需要分配的大小之差小于 44，我们直接将整个空闲块分配掉，否则需要切割出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void place(void *bp, size_t size) {
    size_t bsize = GET_SIZE(HDRP(bp));
    del(bp);
    if (bsize - size >= 4 * WSIZE) {
        PUT(HDRP(bp), PACK(size, 1));
        PUT(FTRP(bp), PACK(size, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(bsize - size, 0));
        PUT(FTRP(bp), PACK(bsize - size, 0));
        ins(bp);
    } else {
        PUT(HDRP(bp), PACK(bsize, 1));
        PUT(FTRP(bp), PACK(bsize, 1));
    }
}

寻找空闲块

寻找空闲块的思路很简单，找到的大小所在的大小类，先搜索这个大小类中是否有合适的块，如果找到就可以返回了。如果没有找到，就向大一级的大小类中继续找，直到找到为止。

这里就是分离适配的组织结构最大的优势了。既避免了在搜索特别小的大小类中浪费时间，也尽可能保证了搜索得到的块是比较小的。

1
2
3
4
5
6
7
void *find_fit(size_t size) {
    for (int list = getlist(size);  list < 20; ++list)
        for (void *bp = GET_HEAD(list); bp; bp = GET_NEXT(bp))
            if (GET_SIZE(HDRP(bp)) >= size)
                return bp;
    return NULL;
}

mm_malloc，mm_free 和 mm_realloc

下面就是本次实验的主角了。

mm_malloc

mm_malloc 的思路很简单，首先将需要分配的大小调整到合适的。这里需要调整的有加上头部和脚部的大小，还有双字对齐，还有如果需要分配的大小小于 44 个字。，那么就将大小改成 44 个字。

然后，使用 find_fit 函数找到合适的空闲块。如果找到就可以调用 place 来分割放置了。如果找不到，就要调用 extend_heap 来扩大堆空间，寻找新的空闲块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void *mm_malloc(size_t size)
{
    if (size == 0) return NULL;
    if (size <= DSIZE) size = 2 * DSIZE;
    else size = size + DSIZE;
    size = (size + DSIZE - 1) / DSIZE * DSIZE;

    void *bp = find_fit(size);
    if (bp != NULL) {
        place(bp, size);
        return bp;
    }

    if ((bp = extend_heap(MAX(size, CHUNKSIZE) / WSIZE)) == NULL) return NULL;
    place(bp, size);
    return bp;
}

mm_free

mm_free 函数比较简单，将这个块的头部、脚部标记为空闲块，调用 coalesce 合并空闲块并插入链表即可。

1
2
3
4
5
6
7
8
void mm_free(void *ptr)
{
    if (ptr == NULL) return;
    size_t size = GET_SIZE(HDRP(ptr));
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    coalesce(ptr);
}

mm_realloc

mm_realloc 函数实验提供的程序中已经完成了，除了查询 size 的一个小问题以外可以直接使用。

大致的思路就是先调用 mm_malloc 分配更大的空间，然后使用 memcpy 将内容复制过去，最后使用 mm_free 释放旧的空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void *mm_realloc(void *ptr, size_t size)
{
    void *oldptr = ptr;
    void *newptr;
    size_t copySize;
    
    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    copySize = GET_SIZE(HDRP(ptr));
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

测试和评分

首次适配版本：

image-20230908135539982

最优适配版本：

image-20230908135557406

可以发现，两种方法的差距其实并不是很大，这可以说明分离适配的策略其实已经足以使得首次适配的空间表现接近最优适配了，也足以让最优适配的时间消耗大大降低。

程序

点击这个 链接 查看程序！

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。