ICS Lab3 Malloc Report

ICS Lab3 Malloc lab实验报告

张凯文 2021010729 计12班 2023年1月15日

基础：隐式空闲链表

隐式空闲链表通过在每个块的头部、脚部各 8 个字节记录块的大小、分配信息维护堆的结构。它通过读取块的大小找到相邻块的位置，因此称为隐式链表。其具体实现在课本上有详细介绍，因此在此只阐述基本思路。

mm_init

首先为序言块（ size = 16 字节，头部脚部各 8 字节，标记已分配 ）和结尾块（ 通过将 size 设为 0 标记结尾，已分配 ）分配空间，记录堆空间起始位置，然后首次扩展堆空间得到一个空闲块。

mm_malloc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void *mm_malloc(size_t size) {
  size_t asize;
  char *bp;
  
  if(size == 0)
    return NULL;

  if(size <= DSIZE)
      asize = 2 * DSIZE;
  else
      asize = ALIGN(size + DSIZE);
  
  if((bp = find_fit(asize)) != NULL) {
    return place(bp, asize);
  }

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

各个版本的 mm_malloc 实现代码相同：首先根据最小块和 16 字节对齐的要求对 size 进行预处理，然后尝试在已分配的堆空间中寻找合适大小的块（find_fit），如果不能找到则扩展堆空间（extend_heap），在相应位置分配内存（place）。不同版本的实现，只需要更改 find_fit 和 place 函数即可。

对于隐式空闲链表的 find_fit 函数，可以采用首次适配（first_fit）、下一次适配（next_fit)、最优适配（best_fit）等方案，在此我实现了前两种：

  • first_fit：每次从堆空间起始位置出发，找到第一个大小充足的空闲块即返回；
  • next_fit：维护一个全局变量 last_fit 记录上一次找到的空闲块位置，下一次寻找从该位置出发遍历堆空间，寻找合适的空闲块。基于 next_fit 实现时，需要注意合并空闲块后要保证 last_fit 不会指向刚刚被合并、已不存在的空闲块。

mm_free

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

各个版本的 mm_free 实现代码也相同，将相应块设为未分配，然后合并相邻空闲块即可。

基于 mm_malloc 和 mm_free 可以实现 mm_realloc 的 naive 版本，基于此实现的基础版本可以通过正确性评测：

但是，由于每次分配空间时都可能遍历整个堆空间，时间复杂度与块总量（包括已分配块和空闲块）线性正比，吞吐量非常低，因此需要改进。

改进：分离式空闲链表

与隐式空闲链表不同，显式空闲链表显式记录每个空闲块的前驱、后继空闲块，因此在搜索空闲块时时间复杂度只与空闲块数量线性正比。

在此基础上，将各个空闲块根据大小再划分为若干等价类，每个等价类独立构成一个链表，就得到了分离式空闲链表。由于事先进行了大小划分，每次寻找一定大小的空闲块时都会从大小相近的空闲块开始寻找，因此对分离式空闲链表进行简单的 first_fit 搜索时，效果与对普通隐式空闲链表或显式空闲链表进行 best_fit 的效果相当，在空间利用率上也会得到显著提升。

下图展示了两类链表中空闲块结构的对比：

在原本隐式空闲链表实现的基础上，需要额外维护分离式空闲链表的结构：

mm_init

在序言块之前分配一块空间存放空闲链表表头，记录各链表第一个空闲块的地址（表为空则为 0）。

freelist_header

根据给定块大小确定表头。链表的数量 LISTSIZE 是一个超参数，理论上来说在一定限度内划分越细致（LISTSIZE越大）效果越好，但由于最大块大小有限，实践中设为 13 ~ 19 得分相差不大，在此设为 15，即根据块大小（单位：字节，最小块 $4 \times 8 = 32$ 字节）划分为 15 个等价类：
$$ [32], \ (32, 64],\ (64,128], \ldots , (2^{17}, 2^{18}],\ (2^{18}, +\infin) $$
根据块大小找到相应等价类即可。

insert_to_freelist

1
2
3
4
5
6
7
8
9
static void insert_to_freelist(void *bp) {
  size_t size = GET_SIZE(HDRP(bp));
  void *header = freelist_header(size);
  void *first = GET_HEAD(header);
  PUT_PRED(bp, 0);
  PUT_SUCC(bp, first);
  if(first) PUT_PRED(first, bp);
  PUT_HEAD(header, bp);
}

将指定块插入空闲链表。在此使用最简单的表头插入方法，在 $O(1)$ 时间内调整表头处拓扑结构，将空闲块插入在链表头即可。

remove_from_freelist

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void remove_from_freelist(void *bp) {
  void *pred = GET_PRED(bp), *succ = GET_SUCC(bp);
  /* bp在表头 */
  if(!pred) {
    size_t size = GET_SIZE(HDRP(bp));
    void *header = freelist_header(size);
    PUT_HEAD(header, succ);
    if(succ) PUT_PRED(succ, 0);
  }
  /* bp不在表头 */
  else {
    PUT_SUCC(pred, succ);
    if(succ) PUT_PRED(succ, pred);
  }
  PUT_PRED(bp, 0);
  PUT_SUCC(bp, 0);
}

调整局部拓扑结构，将指定块从空闲链表中删除。

segregate_fit

1
2
3
4
5
6
7
8
9
10
11
static void *segregate_fit(size_t size) {
  char *header;
  char *bp;
  for(header = freelist_header(size); header != freelistp + LISTSIZE * WSIZE; header += WSIZE) {
    for(bp = GET_HEAD(header); bp; bp = GET_SUCC(bp)) {
      if(GET_SIZE(HDRP(bp)) >= size)
        return bp;
    }
  }
  return NULL;
}

分离式空闲链表的 find_fit 方法。根据指定大小找到相应等价类链表表头，从该链表开始搜索大小充足的块，若该链表中没有则继续到大小更大的等价类链表中搜索，找到第一个合适的块即返回。

此外，还需要修改 coalesce 和 place 等函数，将被合并的空闲块从链表中删除，将新产生的空闲块插入空闲链表，正确维护好空闲链表结构即可。基于分离式空闲链表的内存分配器吞吐量有了巨大提升，但 mm_realloc 函数性能仍然受限，因此还需要重写 mm_realloc 函数。

改进：重写mm_realloc函数

改进的基本思想是：每次通过 mm_malloc 函数重新分配需要花费大量时间寻找合适空闲块，但假如 newsize 本来就比 oldsize 小，或者在附近就有空闲块能给出足够的空间，那么就在原空间附近重新分配即可，还可以减少碎片情况。实在不行，才调用 mm_malloc 函数重新分配空间。

具体处理可参见如下见示意图：

如此改进后，realloc 测试点的吞吐量也得以提升，在调整 CHUNKSIZE 到合适大小后，得分可以提高到 90 分以上：

优化trick

可以发现，当前实现虽然对大部分测试点空间利用率不错，但 8、9 号测试点却只有 50% 左右。通过 gdb 调试可以发现，这两个测试点都是大小块间隔分配（连续相继分配 size = 64、448 / 16、112 的块），这样内部大小块相继分布，释放小块后会出现大量不连续的小块空间难以再利用，造成大量碎片现象。对此，我们可以在 place 函数分割空闲块时，遇大块则放在后面，遇小块则放在前面，从而实现每个 CHUNK 中大小块连续存放，在释放之后也能得到连续的空间。

具体而言，只需要略微修改 place 函数，当分配块的 size 大于 96（配合 CHUNKISZE = 4096 / 8192，综合两个测试点的数据情况，在实践中效果较好） 时，分割空闲块后将分配块放在后面即可。这样做之后，总得分能提升到 94：

不过，这样做之后会发现 11 号测试点空间利用率下降明显，这是由于该测试点反复在与末尾间隔一个小分配块的地方重分配一个较大块，在 CHUNKSIZE 设置较大时会在结尾处出现大块尾部碎片。对此可能可以通过针对性地调整 realloc 策略（如对特定大小块放置到结尾空闲空间）优化，但限于时间原因没有继续实现，未来有空可以继续尝试。