0x1 介绍

可以从手册得知，我们需要修改mm.c里面的三个函数mm_malloc、mm_free、mm_realloc来实现堆的相关功能。教师们为我们编写了如此庞大的测试环境，那么我们也要认真完成它。

由于lab自带的版本是每次请求时都执行sbrk系统调用。我们知道，系统调用会是陷入内核，花费大量时间，那么接下来我们要做的就是减少系统调用的次数。

下图为自带版本的测试，可以看到内存利用率并不高 ，并且有部分测试并未通过。

0x2 隐式空闲列表

我们进行第一次修改，为其实现一个简单的分配器。

注意事项：

  • 这里的块指针bp指向第一个有效载荷

  • 可以利用宏定义将复杂操作定义为类似函数操作的方法（PS：在预处理期间替换，而函数内联等操作则在编译期替换）

  • sbrk返回值

返回值 描述
(void *)-1 调用失败，无法扩展数据段。通常伴随设置errno来描述具体错误。
非空指针 调用成功，返回指向数据段新分配空间的指针。

首先是宏定义，宏定义可以简化操作，避免一些难以察觉的错误。

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
/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)

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

#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12)

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

#define GET(p) (*(unsigned int *)(p))
#define PUT(p, val) (*(unsigned int *)(p) = (val))

#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))

#define PACK(size, alloc) ((size) | (alloc))

static char *heap_listp = 0; //初始堆地址

手册提到，我们可以实现mm_check来检查内存分配器是否在工作。

这里我实现了两个日志函数，log_message_function用来记录函数执行顺序，mm_check用来打印空闲链表，这里的日志会严重影响运行速度，于是使用宏来控制日志的开关。

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
//  #define DEBUG
#ifdef DEBUG
#define log_message(fmt, ...) log_message_function(fmt, __VA_ARGS__)
#define mm_check() mm_check_function()
#else
#define log_message(fmt, ...)
#define mm_check()
#endif

static inline void log_message_function(const char *fmt, ...) {
  FILE *file;
  file = fopen("log.log", "a");
  va_list args;
  va_start(args, fmt);
  vfprintf(file, fmt, args);
  va_end(args);
  fclose(file);
}

static inline void mm_check_function() {
  FILE *file;
  file = fopen("log.log", "a");
  if (file == NULL)
    exit(0);
  fprintf(file, "---------------------链表----------------------");
  fprintf(file, "\n");
  char *p = heap_listp;
  while (GET_SIZE(HDRP(p)) != 0) {
    size_t size = GET_SIZE(HDRP(p));
    size_t alloc = GET_ALLOC(HDRP(p));
    fprintf(file, "pointer：%p   size:%d    alloc:%d\n", p, size, alloc);
    p = NEXT_BLKP(p);
  }
  fprintf(file, "-----------------------------------------------");
  fprintf(file, "\n");
  if (fclose(file) != 0) {
    exit(0);
  }
}

初始化堆空间，主要是分配头部和脚部，使其符合空闲链表的组织方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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 += (4 * WSIZE);

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

  return 0;
}

mm_malloc：首先要将要分配的空间大小进行8字节对齐，调用find_fit函数：

  • 当有空闲空间时，调用place()函数，将此块标记为已分配。
  • 当无空闲空间时，调用 extend_heap函数，增加并合并堆内存，然后调用place()函数。

mm_free:

  • 将已分配的块标记为空闲块，然后调用coalesce()函数，按照下图四种情况进行合并。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
void *mm_malloc(size_t size) {

  log_message("malloc %d\n", size);

  if (size == 0)
    return NULL;

  size_t asize = ALIGN(size + SIZE_T_SIZE); //加入头部尾部并对齐
  size_t extendsize;
  char *bp;

  if ((bp = find_fit(asize)) != NULL) {
    place(bp, asize);
    log_message("malloc:success! pointer:%p   size:%d     alloc:%d  \n\n", bp,
                GET_SIZE(HDRP(bp)), GET_ALLOC(HDRP(bp)));
    mm_check();
    return bp;
  }

  else {
    extendsize = MAX(CHUNKSIZE, asize);
    log_message("We need %d!!!\n", extendsize);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
      return NULL;
    else {
      place(bp, asize);
      log_message("malloc:success! pointer:%p   size:%d     alloc:%d  \n\n", bp,
                  GET_SIZE(HDRP(bp)), GET_ALLOC(HDRP(bp)));
      mm_check();
      return bp;
    }
  }
}

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);
}

void *mm_realloc(void *ptr, size_t size) {

  size_t oldsize;
  void *newptr;

  if (size == 0) {
    mm_free(ptr);
    return 0;
  }

  if (ptr == NULL) {
    return mm_malloc(size);
  }

  newptr = mm_malloc(size);

  if (!newptr) {
    return 0;
  }

  oldsize = GET_SIZE(HDRP(ptr));
  if (size < oldsize)
    oldsize = size;
  memcpy(newptr, ptr, oldsize);

  mm_free(ptr);

  return newptr;
}

接下来的则是各种子函数，主要是注意堆操作的方式，仔细检查。在这里，log_message()可以帮助我们调试，快速确定合并方式，执行结果，函数执行顺序等重要方式。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
static inline void *coalesce(void *bp) {
  size_t prev_alloc = GET_ALLOC(HDRP(PREV_BLKP(bp)));
  size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
  size_t size = GET_SIZE(HDRP(bp));

  if (prev_alloc && next_alloc) { /* case 1 */
    log_message("coalesce: case 1   pointer:%p\n", bp);
    return bp;
  } else if (prev_alloc && !next_alloc) { /* case 2 */
    size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    log_message("coalesce: case 2   pointer:%p\n", bp);
  }

  else if (!prev_alloc && next_alloc) { /* case 3 */
    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);

    log_message("coalesce: case 3   pointer:%p\n", bp);
  }

  else if (!prev_alloc && !next_alloc) { /* case 4 */
    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));
    log_message("coalesce: case 4   pointer:%p\n", bp);
  }
  return bp;
}

static inline char *find_fit(size_t asize) {
  char *p = heap_listp;
  while (GET_SIZE(HDRP(p)) != 0) {
    size_t size = GET_SIZE(HDRP(p));
    size_t alloc = GET_ALLOC(HDRP(p));

    if (!alloc && size >= asize) {
      log_message("fit_block   poniter:%p size:%d   alloc:%d\n", p, size,
                  alloc);
      return p;
    }

    p = NEXT_BLKP(p);
  }
  return NULL;
}

static inline void place(char *ptr, size_t asize) {
  size_t size = GET_SIZE(HDRP(ptr));
  if ((size - asize) >= (2 * DSIZE)) {
    PUT(HDRP(ptr), PACK(asize, 1));
    PUT(FTRP(ptr), PACK(asize, 1));

    ptr = NEXT_BLKP(ptr);
    PUT(HDRP(ptr), PACK(size - asize, 0));
    PUT(FTRP(ptr), PACK(size - asize, 0));
  } else {
    PUT(HDRP(ptr), PACK(size, 1));
    PUT(FTRP(ptr), PACK(size, 1));
  }
}

static inline 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)) == -1)
    return NULL;

  PUT(HDRP(bp), PACK(size, 0));
  PUT(FTRP(bp), PACK(size, 0));
  PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
  log_message("extend_heap:   pointer:%p  size:%d \n", bp, size);
  return coalesce(bp);
}

让我们来测试一下，可以看到我们的分数成功来到了64分！

0x3 显式空闲列表

接下来进行我们的改进！在空闲块内添加前驱后继指针，当需要空闲块时，直接通过指针直接访问下一节点，而不是需要先获取头部信息计算偏移。这种方法可以加快分配速度，但是在释放块时需要线性时间来搜索前驱。那么这样到底可以提升多少访问速度呢，我们使用后进先出的LIFO顺序维护链表。

利用宏定义来快速获取和放置前驱和后继指针， 同时定义插入和删除函数，简化对链表的操作。

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
/* 获取指针 */
#define GET_PRED(bp) (*(char **)(bp))
#define GET_SUCC(bp) (*(char **)((char *)(bp) + WSIZE))

/* 放置指针 */
#define PUT_PRED(bp, pred) (*(char **)(bp) = (pred))
#define PUT_SUCC(bp, succ) (*(char **)((char *)(bp) + WSIZE) = (succ))
static char *free_listp = NULL;

static void insert_free_block(char *bp) {

    if (free_listp != NULL) {
        PUT_PRED(bp, NULL);
        PUT_SUCC(bp, free_listp);
        PUT_PRED(free_listp, bp);
    } else {
        PUT_PRED(bp, NULL);
        PUT_SUCC(bp, NULL);
    }
    free_listp = bp;
}

static void remove_free_block(char *bp) {
  char *pred = GET_PRED(bp);
  char *succ = GET_SUCC(bp);
  //当前块不为列表头部
  if (pred != NULL) {
    PUT_SUCC(pred, succ);
  } else {
    free_listp = succ;
  }
  //判断是否有后继，将前驱添加到后继中
  if (succ != NULL) {
    PUT_PRED(succ, pred);
  }
}

重写mm_check_function()检测空闲链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static  void mm_check_function() {
  FILE *file;
  file = fopen("log.log", "a");

  char *p = free_listp;
  fprintf(file, "\n\n====================空闲链表======================\n");
  while (p != NULL) {
    size_t size = GET_SIZE(HDRP(p));
    size_t alloc = GET_ALLOC(HDRP(p));
    fprintf(file, "pointer：%p  pre:%p   succ:%p  size:%d    alloc:%d\n", p,GET_PRED(p), GET_SUCC(p), size, alloc);
    p = GET_SUCC(p);
  }
  fprintf(file, "\n====================空闲链表======================\n\n\n");


  if (fclose(file) != 0) {
    exit(0);
  }
}

实现的三大函数只需在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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

/*
 * mm_init - initialize the malloc package.
 */
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 += (4 * WSIZE);
     free_listp = NULL;  // 初始化 free_listp
  if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
    return -1;

  return 0;
}

/*
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */
void *mm_malloc(size_t size) {

  log_message("malloc %d\n", size);

  if (size == 0)
    return NULL;

  size_t asize = ALIGN(size + SIZE_T_SIZE); //加入头部尾部并对齐
  size_t extendsize;
  char *bp;

  if ((bp = find_fit(asize)) != NULL) {
    place(bp, asize);
    log_message("malloc:success! pointer:%p   size:%d     alloc:%d  \n\n", bp,
                GET_SIZE(HDRP(bp)), GET_ALLOC(HDRP(bp)));
    mm_check();
    return bp;
  }

  else {
    extendsize = MAX(CHUNKSIZE, asize);
    log_message("We need %d!!!\n", extendsize);
    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
      return NULL;
    else {
      place(bp, asize);
      log_message("malloc:success! pointer:%p   size:%d     alloc:%d  \n\n", bp,
                  GET_SIZE(HDRP(bp)), GET_ALLOC(HDRP(bp)));
      mm_check();
      return bp;
    }
  }
}

/*
 * mm_free - Freeing a block does nothing.
 */
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));
  insert_free_block(ptr);
  coalesce(ptr);
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size) {

  size_t oldsize;
  void *newptr;

  if (size == 0) {
    mm_free(ptr);
    return 0;
  }

  if (ptr == NULL) {
    return mm_malloc(size);
  }

  newptr = mm_malloc(size);

  if (!newptr) {
    return 0;
  }

  oldsize = GET_SIZE(HDRP(ptr));
  if (size < oldsize)
    oldsize = size;
  memcpy(newptr, ptr, oldsize);

  mm_free(ptr);

  return newptr;
}

注意区分已分配的块和未分配的块，

只有未分配的块才需要添加前驱和后继指针，已分配的块需要及时去除前驱和后继指针。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
static  inline void *coalesce(void *bp) {
  size_t prev_alloc = GET_ALLOC(HDRP(PREV_BLKP(bp)));
  size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
  size_t size = GET_SIZE(HDRP(bp));

  if (prev_alloc && next_alloc) { /* case 1 */
    log_message("coalesce: case 1   pointer:%p\n", bp);
    return bp;
  } else if (prev_alloc && !next_alloc) { /* case 2 */
    size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
    remove_free_block(bp);
    remove_free_block(NEXT_BLKP(bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    insert_free_block(bp);
    log_message("coalesce: case 2   pointer:%p\n", bp);
  }
  
  else if (!prev_alloc && next_alloc) { /* case 3 */
    remove_free_block(bp);
    remove_free_block(PREV_BLKP(bp));
    size += GET_SIZE(HDRP(PREV_BLKP(bp)));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
    insert_free_block(PREV_BLKP(bp));
    bp = PREV_BLKP(bp);
    log_message("coalesce: case 3   pointer:%p\n", bp);
  }

  else if (!prev_alloc && !next_alloc) { /* case 4 */
    remove_free_block(PREV_BLKP(bp));
    remove_free_block(bp);
    remove_free_block(NEXT_BLKP(bp));
    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);
    insert_free_block(bp);
    log_message("coalesce: case 4   pointer:%p\n", bp);
  }
  return bp;
}

static inline char *find_fit(size_t asize) {
  char *p = free_listp;
  while (p != NULL) {
    size_t size = GET_SIZE(HDRP(p));
    size_t alloc = GET_ALLOC(HDRP(p));
    if (!alloc && size >= asize) {
      log_message("fit_block   poniter:%p size:%d   alloc:%d\n", p, size, alloc);
      return p;
    }
    p = GET_SUCC(p);
  }
  return NULL;
}

static inline void place(char *ptr, size_t asize) {
  size_t size = GET_SIZE(HDRP(ptr));
  if ((size - asize) >= (2 * DSIZE)) {
    PUT(HDRP(ptr), PACK(asize, 1));
    PUT(FTRP(ptr), PACK(asize, 1));
    remove_free_block(ptr);   // 将已分配的块从空闲块列表中移除
    char *next_ptr = NEXT_BLKP(ptr);
    PUT(HDRP(next_ptr), PACK(size - asize, 0));
    PUT(FTRP(next_ptr), PACK(size - asize, 0));   
    insert_free_block(next_ptr);    // 将剩余的部分作为空闲块插入列表
  } else {
    PUT(HDRP(ptr), PACK(size, 1));
    PUT(FTRP(ptr), PACK(size, 1));
    remove_free_block(ptr);   // 将已分配的块从空闲块列表中移除
  }

}

static inline 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)) == -1)
    return NULL;

  PUT(HDRP(bp), PACK(size, 0));
  PUT(FTRP(bp), PACK(size, 0));
  PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
  log_message("extend_heap:   pointer:%p  size:%d \n", bp, size);
  insert_free_block(bp);
  mm_check();
  return coalesce(bp);
}

可以看到虽然内存利用率有些许下降，但是我们分配速度得到了快速的提升！！！那么，82也算是优秀了吧(👉ﾟヮﾟ)👉。

0x4分离空闲列表

将不同大小的空闲列表分割，将分配时查找空闲块的时间变为匹配不同大小链表的时间，当空闲块很多时，可以显著提高分配器的效率。

这里先标记为TODO，希望以后有时间会回来做。