计算机系统概论 Lab 3

实验目的

• 使用 $C$ 语言实现一个 $Dynamic$ $Storage$ $Allocater$.
• 实现并优化 $malloc$, $free$, $realloc$ 等功能.
• 熟练 $gdb$ 调试技巧.

最终性能

在最终提交的版本中, 我对 $mm.c$ 的相关实现策略如下:

Data Structure -------- Explicit Free List (Double Linked List)
  / Allocated Block --- Header, Payload and Footer
  \ Free Block -------- Header, Pred_ptr, Succ_ptr and Footer
Fit Strategy ---------- First Fit
Coalesce Strategy ----- Immediate Coalesce
Realloc Strategy ------ First Try to Coalesce, Then Try to Malloc and Free

最终实现的性能如下:

Results for mm malloc:

Score = (46 (util) + 40 (thru)) * 11/11 (testcase) = 86/100

Version 0

$Version$ $0$ 为未作任何修改的原始 $mm.c$ 文件, 直接进行测试的结果.

Block Structure

在原始 $mm.c$ 文件中, 一个 $block$ 没有 $header$ 或 $footer$ 标记, 也不会被 $coalesce$ 或 $reuse$.

Helper Functions

• 没有实现任何 $helper$ $function$ 以辅助进行内存块的分配.
• 所有内存块不进行 $coalesce$, 经过 $free$ 后不会被 $malloc$ 或 $realloc$ 复用.

Malloc Functions

mm_init

• 不进行 $init$, 直接返回.

mm_malloc

• 将 $size$ 对齐至 $16$ 字节, 直接调用 $mem_sbrk$ 申请新的堆区域, 并返回一个指向连续内存块的指针.

mm_free

• 不进行 $free$, 直接返回.

mm_realloc

• 直接调用 $mm_malloc$ 分配 $newptr$.
• 如果 $newptr$ 为 $NULL$, 此时堆可扩展内存不足, 直接返回 $NULL$.
• 否则, 依据大小关系将 $ptr$ 指向的旧内存块内容复制到 $newptr$ 指向的新块.

Performance

Results for mm malloc:
trace            name     valid  util     ops      secs   Kops
 1     amptjp-bal.rep       yes   23%    5694  0.000070  81459
 2       cccp-bal.rep       yes   19%    5848  0.000072  81110
 3    cp-decl-bal.rep       yes   30%    6648  0.000084  78768
 4       expr-bal.rep       yes   40%    5380  0.000066  82137
 5 coalescing-bal.rep        no     -       -         -      -
 6     random-bal.rep        no     -       -         -      -
 7    random2-bal.rep        no     -       -         -      -
 8     binary-bal.rep       yes   54%   12000  0.000144  83624
 9    binary2-bal.rep       yes   47%   24000  0.000186 128755
10    realloc-bal.rep        no     -       -         -      -
11   realloc2-bal.rep        no     -       -         -      -
Total                               -       -         -      -

Score = (12 (util) + 40 (thru)) * 6/11 (testcase) = 28/100

此时实现的分配器尚不能正确实现所有任务.

$Kops$ 满足要求, 但 $Memory$ $Utilization$ 过低.

Version 1

参考 $CSAPP3e$ : $9.9.12$ 中的实现, 采用 $Implicit$ $Free$ $List$ 组织空闲块.

Block Structure

一个 $block$ 的结构被组织为:

考虑 $Boundary$ $Tags$ 与 $Alignment$ 条件, 此时 $minimum$ $block$ $size$ 为 $4 * WSIZE\,(32\,Bytes)$.

$Implicit$ $Free$ $List$ 被组织为:

其中 $heap_listp$ 初始默认指向 $Prologue$ $Block$, 而 $Epilogue$ $Block$ 在进行 $coalesce$ 时可以用于消除边界条件.

Macros

相关 $Macro$ $Definition$ 完全参考了 $CSAPP3e$ : $9.9.12$ 中的实现.

Helper Functions

first_fit

static void *first_fit(size_t asize){
  for (bp = heap_lo; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
    if (!GET_ALLOC(HDRP(bp)) && (GET_SIZE(HDRP(bp)) >= asize))
      return bp;
  return NULL;
}

• 采用 $first$ $fit$ 查询 $free$ $block$, 其中 $heap_lo$ 为定义的 $Implicit$ $Free$ $List$ 的起始地址.
• 若 $no$ $fit$, 则返回 $NULL$.

place

static void place(void *bp, size_t asize) {
  size_t size = GET_SIZE(HDRP(bp));  
  if ((size - asize) >= (4 * WSIZE)) {
    PUT(HDRP(bp), PACK(asize,1));
    PUT(FTRP(bp), PACK(asize,1));
    PUT(HDRP(NEXT_BLKP(bp)), PACK(size - asize,0));
    PUT(FTRP(NEXT_BLKP(bp)), PACK(size - asize,0));
  } 
  else {
    PUT(HDRP(bp), PACK(size,1));
    PUT(FTRP(bp), PACK(size,1));
  }
}

• 将大小为 $asize$ 的块放置在 $bp$ 指向的 $free$ $block$ 处.
• 由于 $minimum$ $block$ $size$ 为 $4 * WSIZE$, 若剩余 $payloader$ 的 $size$ 过大, 则进行 $split$ 操作产生一个新的 $free$ $block$.

coalesce

static 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 */
    return bp;
  } else if (prev_alloc && !next_alloc) {   /* Case 2 */
    ...
  } else if (!prev_alloc && next_alloc) {   /* Case 3 */
    ...
  } else {								  	/* Case 4 */
    ...
  }
  return bp;
}

• 采用 $immediate$ $coalesce$ 策略.
• 使用 $header$, $footer$ 作为 $boundary$ $tag$ 进行标记, 根据前后块的 $alloc$ $bit$ 位进行 $free$ $block$ 的合并.

extend_heap

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)) == -1)
    return NULL;
  PUT(HDRP(bp), PACK(size, 0)); 		/* Free block header */
  PUT(FTRP(bp), PACK(size, 0)); 		/* Free block footer */
  PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */
  return coalesce(bp);
}

• 用大小为 $size$ 的双字对齐的 $free$ $block$ 扩展堆.
• $epilogue$ $block$ 的 $size$ 为 $0$, $alloc$ $bit$ 位置为 $1$.
• 使用 $mem_sbrk$ 分配一个双字对齐块后, $epilogue$ $block$ 变成了 $new$ $free$ $block$ $header$, 下一 $block$ $header$ 特殊化为 $new$ $epilogue$ $block$.

Malloc Functions

mm_init

int mm_init(void) { 
  if ((heap_lo = mem_sbrk(4 * WSIZE)) == (void *)-1)
    return -1;
  PUT(heap_lo, 0);
  PUT(heap_lo + (1 * WSIZE), PACK(DSIZE, 1));
  PUT(heap_lo + (2 * WSIZE), PACK(DSIZE, 1));
  PUT(heap_lo + (3 * WSIZE), PACK(0, 1));
  heap_lo += (2 * WSIZE);
  if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
    return -1;
  return 0;
}

• 设置 $prologue$ $block$, $epilogue$ $block$.
• 用 $CHUNKSIZE$ 大小的 $free$ $block$ 扩展空堆, 若扩展失败则返回 $NULL$.

mm_malloc

void *mm_malloc(size_t size) {
  size_t asize;
  char *bp;
  
  if (size == 0) return NULL;
  /* Adjust block size to include overhead and alignment reqs. */
  if (size <= DSIZE) asize = 2 * DSIZE;
  else asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
  /* Search the free list for a fit */
  if ((bp = first_fit(asize))) {
    place(bp, asize);
    return bp;
  }
  /* No fit found. Get more memory and place the block */
  if (!(bp = extend_heap(MAX(asize, CHUNKSIZE) / WSIZE)))
    return NULL;
  place(bp, asize);
  return bp;
}

• 将 $size$ 对齐至 $16$ 字节, 并扩展加上 $header$, $footer$.
• 首先使用 $first$ $fit$ 策略查询 $free$ $list$, 返回一个指向连续内存块的指针.
• 若返回为 $NULL$, 则在该处进行 $extend_heap$.

mm_free

void mm_free(void *ptr) {
  size_t size = GET_SIZE(HDRP(ptr));
  PUT(HDRP(ptr), PACK(size, 0));
  PUT(FTRP(ptr), PACK(size, 0));
  coalesce(ptr);
}

• 将 $alloc$ $bit$ 位置 $0$, 并进行 $free$ $block$ 的合并.

mm_realloc

• 如果 $ptr$ 为 $NULL$, 直接调用 $mm_malloc$.
• 如果 $size$ 为 $0$, 直接调用 $mm_free$.
• 否则, 直接调用 $mm_malloc$ 分配 $newptr$, 以下同 $Version$ $0$.

Performance

Results for mm malloc:
trace            name     valid  util     ops      secs   Kops
 1     amptjp-bal.rep       yes   90%    5694  0.001877   3033
 2       cccp-bal.rep       yes   92%    5848  0.001071   5459
 3    cp-decl-bal.rep       yes   94%    6648  0.004788   1389
 4       expr-bal.rep       yes   96%    5380  0.005364   1003
 5 coalescing-bal.rep       yes   50%   14400  0.000173  83189
 6     random-bal.rep       yes   90%    4800  0.006984    687
 7    random2-bal.rep       yes   87%    4800  0.006384    752
 8     binary-bal.rep       yes   54%   12000  0.015309    784
 9    binary2-bal.rep       yes   47%   24000  0.007432   3229
10    realloc-bal.rep       yes   32%   14401  0.141429    102
11   realloc2-bal.rep       yes   34%   14401  0.003931   3663
Total                             70%  112372  0.194743    577

Score = (42 (util) + 2 (thru)) * 11/11 (testcase) = 44/100

通过了所有测试文件.

几乎所有测试点的 $Kops$ 均需进行优化, 最后两个测试 $mm_realloc$ 功能点的 $Memory$ $Utilization$ 过低.

Version 2

采用 $Explicit$ $Free$ $List$ 组织空闲块, 使用的数据结构为 $Double$ $Linked$ $List$.

Block Structure

一个 $block$ 的结构被组织为:

考虑 $Boundary$ $Tags$ 与 $Alignment$ 条件, 此时 $minimum$ $block$ $size$ 为 $4 * WSIZE\,(32\,Bytes)$.

Macros

/* 前/后 block 中 payloader 的起始地址 */
#define PREV_BLK(bp)  ((void *)(bp) - GET_SIZE((void *)(bp) - DSIZE))
#define NEXT_BLK(bp)  ((void *)(bp) + GET_SIZE(HEADER(bp)))

/* 前/后 free block 中 payloader 的起始地址 */
#define PRED_BLK(bp)  (*(void **)(bp))
#define SUCC_BLK(bp)  (*(void **)(bp + WSIZE))

• 模拟了 $Double$ $Linked$ $List$ 的实现.
• $PRED_BLK$, $SUCC_BLK$ 区别于先前定义的 $PREV_BLK$, $NEXT_BLK$, 用于在 $Explicit$ $Free$ $List$ 中进行前后 $free$ $block$ 的标记.

Helper Functions

insert_free_block

static void insert_free_block(void *bp){
  PRED_BLK(bp) = NULL;
  SUCC_BLK(bp) = heap_lo;
  PRED_BLK(sentinel) = bp; 
  heap_lo = bp; 
}

• 将 $bp$ ( 指向一个 $free$ $block$ ) 插入 $Explicit$ $Free$ $List$ 的尾部作为 $sentinel$.

remove_free_block

static void remove_free_block(void *bp){
  PRED_BLK(SUCC_BLK(bp)) = PRED_BLK(bp);
  if (PRED_BLK(bp))  
    SUCC_BLK(PRED_BLK(bp)) = SUCC_BLK(bp); 
  else
    heap_lo = SUCC_BLK(bp);
}

• 将 $bp$ ( 指向一个被分配的 $block$ ) 从 $Explicit$ $Free$ $List$ 中删除.
• 需要检查 $bp$ 是否为 $sentinel$.

first_fit

static void *first_fit(size_t asize){
  ...
  if(malloced != asize) counter = 0;
  else if(counter >= 48) {
    bp = extend_heap(MAX(asize / WSIZE, 4));
    return bp;
  } else counter++;
  ...
}

在 $binary{-}bal.rep$ 与 $binary2{-}bal.rep$ 测试文件中进行了大量相同 $size$ 的 $malloc$ 操作.

如果重复使用 $first_fit$ 进行检索, 会使 $Kops$ 显著过低.

• 定义 $malloced$ 为上一次调用 $mm_malloc$ 分配的 $size$ 大小.
• 如果重复分配同样 $size$ 的块超过 $48$ 次 ( $48$ 为反复调节获得的最佳参数 ), 则直接调用 $extend_heap$ 将堆扩展相应大小, 不再通过 $first_fit$ 进行检索.

place

• 若剩余 $payloader$ 需要进行 $split$ 操作, 则先进行 $remove_free_block$, 最后对剩余 $free$ $block$ 进行 $insert_free_block$.
• 否则, 直接进行 $remove_free_block$ 并设置 $alloc$ $bit$.

coalesce

• 仍采用 $immediate$ $coalesce$ 策略.
• 在设置 $alloc$ $bit$ 前进行 $remove_free_block$, 最后对合并的 $free$ $block$ 进行 $insert_free_block$.

extend_heap

• 由于此时 $minimum$ $block$ $size$ 为 $4 WSIZE$, 将 $size$ 双字对齐后, 若其为 $2 WSIZE$, 则置为 $4 * WSIZE$.

Malloc Functions

mm_init

int mm_init(void) { 
  ...
  if (extend_heap(4) == NULL)
    return -1;
  return 0;
}

$mm_init$ 会调用 $extend_heap$ 预分配一块 $4096\,Bytes$ 大小的空间做为起始 $free$ $block$, $mm_malloc$ 在 $List$ 中没有合适 $free$ $block$ 的情况下总会调用 $extend_heap$ 扩展空间, 其大小取 $4096\,Bytes$ 与待分配大小中较大者.

在 $coalescing{-}bal.rep$ 中, 起始分配 $4095\,Bytes$ 大小的空间, 经过 $16$ 字节对齐和 $Tag$ 扩展后大于 $4096\,Bytes$, 初始的 $4096\,Bytes$ 空间永远不会被利用.

只需修改 $mm_init$ 中 $extend_heap$ 初始扩展大小为 $minimun$ $block$ $size$ 即可.

• 用 $minimun$ $block$ $size$ ( $4$ ) 大小的 $free$ $block$ 扩展空堆, 若扩展失败则返回 $NULL$.

mm_realloc

void *mm_realloc(void *bp, size_t size){
  if(size == 0) { mm_free(bp); return NULL; } 
  size_t oldsize = GET_SIZE(HEADER(bp));
  size_t newsize = size + 2 * WSIZE;
    
  if(newsize <= oldsize) return bp; 
  size_t next_alloc = GET_ALLOC(HEADER(NEXT_BLK(bp))); 
  size_t asize = oldsize + GET_SIZE(HEADER(NEXT_BLK(bp)));
  if(!next_alloc && (asize >= newsize)) { 
    remove_free_block(NEXT_BLK(bp)); 
    PUT(HEADER(bp), PACK(asize, 1)); 
    PUT(FOOTER(bp), PACK(asize, 1)); 
    return bp; 
  }
  else {
    void *newbp = mm_malloc(newsize);  
    place(newbp, newsize);
    memcpy(newbp, bp, newsize); 
    mm_free(bp); 
    return newbp; 
  }   
} 

原始的 $mm_realloc$ 没有考虑被分配块前后 $free$ $block$ 的情况, 以及 $new$ $block$ $size$ 和 $old$ $block$ $size$ 的比较, 需对此进行优化.

• 如果 $size$ 为 $0$, 直接调用 $mm_free$.
• 如果 $new$ $block$ $size$ 不大于 $old$ $block$ $size$, 直接返回原指针 $bp$ 即可.
• 否则, 需要考察后面邻块.
  • 若其未分配, 且 $size$ 和不小于 $newsize$, 则直接合并两个 $free$ $block$ 即可.
  • 否则, 需通过 $mm_malloc$ 分配 $new$ $block$, 并进行内存 $memcpy$.

Performance

Results for mm malloc:
trace            name     valid  util     ops      secs   Kops
 1     amptjp-bal.rep       yes   88%    5694  0.000291  19594
 2       cccp-bal.rep       yes   86%    5848  0.000208  28142
 3    cp-decl-bal.rep       yes   94%    6648  0.000386  17214
 4       expr-bal.rep       yes   96%    5380  0.000287  18739
 5 coalescing-bal.rep       yes   98%   14400  0.000202  71111
 6     random-bal.rep       yes   88%    4800  0.000645   7442
 7    random2-bal.rep       yes   85%    4800  0.000747   6429
 8     binary-bal.rep       yes   54%   12000  0.000393  30519
 9    binary2-bal.rep       yes   47%   24000  0.000480  50042
10    realloc-bal.rep       yes   86%   14401  0.000233  61754
11   realloc2-bal.rep       yes   17%   14401  0.000186  77383
Total                             76%  112372  0.004058  27692

Score = (46 (util) + 40 (thru)) * 11/11 (testcase) = 86/100

感悟

• $Malloc$ $Lab$ 需要用心 $DEBUG$, 并考验 $gdb$ 的使用掌握.
• 我从最简单的实现 —— $Implicit$ $Free$ $List$ 开始, 最后选择了 $Explicit$ $Free$ $List$ 进行实现.
• 根据不同 $trace$ 的组成, 我进行了分析与优化, 与 $Segmentation$ $Fault$ 日夜作战.
• 这次 $Lab$ 确实是对我的一次难得的体验!