[施工完成] CSAPP Malloc lab

Posted by 111qqz on Sunday, March 14, 2021

TOC

背景

动手实现一个memory allocator,体会core到爆炸的乐趣(不是

trace file 结构分析

trace file 是对allocator的输入的描述,可以从mdriver.c中的

static trace_t *read_trace(char *tracedir, char *filename);

看到Parse的逻辑,从而得到trace file的结构。

  fscanf(tracefile, "%d", &(trace->sugg_heapsize)); /* not used */
  fscanf(tracefile, "%d", &(trace->num_ids));
  // 似乎只有num_ops用到了。。
  fscanf(tracefile, "%d", &(trace->num_ops));
  fscanf(tracefile, "%d", &(trace->weight)); /* not used */

trace file起始位置的4个数的含义,其中第二个和第三个比较重要。 num_ids表示一共有多少个不同的内存块(对应后续的指令可以显示指定操作哪个内存块,从而确保allocator对malloc和free的顺序没有任何依赖的保证),num_ops表示操作数,也就是malloc(对应'a’),realloc(对应'r’),free(对应'f’)三种操作的个数。

 while (fscanf(tracefile, "%s", type) != EOF) {
    switch (type[0]) {
      case 'a':
        fscanf(tracefile, "%u %u", &index, &size);
        trace->ops[op_index].type = ALLOC;
        trace->ops[op_index].index = index;
        trace->ops[op_index].size = size;
        max_index = (index > max_index) ? index : max_index;
        break;
      case 'r':
        fscanf(tracefile, "%u %u", &index, &size);
        trace->ops[op_index].type = REALLOC;
        trace->ops[op_index].index = index;
        trace->ops[op_index].size = size;
        max_index = (index > max_index) ? index : max_index;
        break;
      case 'f':
        fscanf(tracefile, "%ud", &index);
        trace->ops[op_index].type = FREE;
        trace->ops[op_index].index = index;
        break;
      default:
        printf("Bogus type character (%c) in tracefile %s\n", type[0], path);
        exit(1);
    }
    op_index++;
  }

对于每一个操作,如果是malloc/relloc, 后面两个参数分别表示操作几号内存块,以及需要分配的内存大小是多少。如果是free,则只有一个参数,表示要操作几号内存块

implicit free list

这种也就是CS:APP3e text中着重描述的那种,补充了一些checker逻辑,放在这里作为baseline

结构图如下: 98e0f58b268ec352f4362bbb4f58f8fa.png

这种是带一个boundary tag的,也就是一个footer. footer完全是header内容的副本。 这样做的好处是可以很容易从当前block找到上一个block,只需要常数复杂度的操作,否则需要O(n)复杂度整个遍历一遍。 对应的代价是有效载荷的比例变低了。


int mm_init(void) {
  /* Create the initial empty heap */
  if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)  // line:vm:mm:begininit
    return -1;
  PUT(heap_listp, 0);                            /* Alignment padding */
  PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* Prologue header */
  PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
  PUT(heap_listp + (3 * WSIZE), PACK(0, 1));     /* Epilogue header */
  heap_listp += (2 * WSIZE);                     // line:vm:mm:endinit
  /* $end mminit */

#ifdef NEXT_FIT
  rover = heap_listp;
#endif
  /* $begin mminit */

  /* Extend the empty heap with a free block of CHUNKSIZE bytes */
  if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1;
  //   checkheap(1);
  return 0;
}
/* $end mminit */

/*
 * mm_malloc - Allocate a block with at least size bytes of payload
 */
/* $begin mmmalloc */
void *mm_malloc(size_t size) {
  size_t asize;      /* Adjusted block size */
  size_t extendsize; /* Amount to extend heap if no fit */
  char *bp;

  /* $end mmmalloc */
  if (heap_listp == 0) {
    mm_init();
  }
  /* $begin mmmalloc */
  /* Ignore spurious requests */
  if (size == 0) return NULL;

  /* Adjust block size to include overhead and alignment reqs. */
  if (size <= DSIZE)    // line:vm:mm:sizeadjust1
    asize = 2 * DSIZE;  // line:vm:mm:sizeadjust2
  else
    asize = DSIZE *
            ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);  // line:vm:mm:sizeadjust3

  /* Search the free list for a fit */
  if ((bp = find_fit(asize)) != NULL) {  // line:vm:mm:findfitcall
    place(bp, asize);                    // line:vm:mm:findfitplace
    return bp;
  }

  /* No fit found. Get more memory and place the block */
  extendsize = MAX(asize, CHUNKSIZE);  // line:vm:mm:growheap1
  if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
    return NULL;     // line:vm:mm:growheap2
  place(bp, asize);  // line:vm:mm:growheap3
  mm_checkheap(0);

  return bp;
}
/* $end mmmalloc */

/*
 * mm_free - Free a block
 */
/* $begin mmfree */
void mm_free(void *bp) {
  /* $end mmfree */
  if (bp == 0) return;

  /* $begin mmfree */
  size_t size = GET_SIZE(HDRP(bp));
  /* $end mmfree */
  if (heap_listp == 0) {
    mm_init();
  }
  /* $begin mmfree */

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

/* $end mmfree */
/*
 * coalesce - Boundary tag coalescing. Return ptr to coalesced block
 */
/* $begin mmfree */
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));

  if (prev_alloc && next_alloc) { /* Case 1 */
    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));
  }

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

  else { /* 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));
    bp = PREV_BLKP(bp);
  }
  /* $end mmfree */
#ifdef NEXT_FIT
  /* Make sure the rover isn't pointing into the free block */
  /* that we just coalesced */
  if ((rover > (char *)bp) && (rover < NEXT_BLKP(bp))) rover = bp;
#endif
  /* $begin mmfree */
  return bp;
}
/* $end mmfree */

/*
 * mm_realloc - Naive implementation of realloc
 */
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;
}

/*
 * mm_checkheap - Check the heap for correctness
 */
void mm_checkheap(int verbose) { checkheap(verbose); }

/*
 * The remaining routines are internal helper routines
 */

/*
 * extend_heap - Extend heap with free block and return its block pointer
 */
/* $begin mmextendheap */
static void *extend_heap(size_t words) {
  char *bp;
  size_t size;

  /* Allocate an even number of words to maintain alignment */
  size = (words % 2) ? (words + 1) * WSIZE
                     : words * WSIZE;                  // line:vm:mm:beginextend
  if ((long)(bp = mem_sbrk(size)) == -1) return NULL;  // line:vm:mm:endextend

  /* Initialize free block header/footer and the epilogue header */
  PUT(HDRP(bp), PACK(size, 0));
  /* Free block header */  // line:vm:mm:freeblockhdr
  PUT(FTRP(bp), PACK(size, 0));
  /* Free block footer */  // line:vm:mm:freeblockftr
  PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
  /* New epilogue header */  // line:vm:mm:newepihdr

  /* Coalesce if the previous block was free */
  return coalesce(bp);  // line:vm:mm:returnblock
}
/* $end mmextendheap */

/*
 * place - Place block of asize bytes at start of free block bp
 *         and split if remainder would be at least minimum block size
 */
/* $begin mmplace */
/* $begin mmplace-proto */
static void place(void *bp, size_t asize)
/* $end mmplace-proto */
{
  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));
  }
}
/* $end mmplace */

/*
 * find_fit - Find a fit for a block with asize bytes
 */
/* $begin mmfirstfit */
/* $begin mmfirstfit-proto */
static void *find_fit(size_t asize)
/* $end mmfirstfit-proto */
{
  /* $end mmfirstfit */

#ifdef NEXT_FIT
  /* Next fit search */
  char *oldrover = rover;

  /* Search from the rover to the end of list */
  for (; GET_SIZE(HDRP(rover)) > 0; rover = NEXT_BLKP(rover))
    if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover))))
      return rover;

  /* search from start of list to old rover */
  for (rover = heap_listp; rover < oldrover; rover = NEXT_BLKP(rover))
    if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover))))
      return rover;

  return NULL; /* no fit found */
#else
  /* $begin mmfirstfit */
  /* First-fit search */
  void *bp;

  for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
    if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
      return bp;
    }
  }
  return NULL; /* No fit */
#endif
}
/* $end mmfirstfit */

static void printblock(void *bp) {
  size_t hsize, halloc, fsize, falloc;

  checkheap(0);
  hsize = GET_SIZE(HDRP(bp));
  halloc = GET_ALLOC(HDRP(bp));
  fsize = GET_SIZE(FTRP(bp));
  falloc = GET_ALLOC(FTRP(bp));

  if (hsize == 0) {
    printf("%p: EOL\n", bp);
    return;
  }

  printf("%p: header: [%ld:%c] footer: [%ld:%c]\n", bp, hsize,
         (halloc ? 'a' : 'f'), fsize, (falloc ? 'a' : 'f'));
}

static void checkblock(void *bp) {
  if ((size_t)bp % 8) printf("Error: %p is not doubleword aligned\n", bp);
  if (GET(HDRP(bp)) != GET(FTRP(bp)))
    printf("Error: header does not match footer\n");
  // check last 3 bit: 001 or 000
  int last_three_bit_value = GET_LAST_THREE_BIT(HDRP(bp));
  printf("last three bit value:%d\n", last_three_bit_value);
  if (last_three_bit_value != 0 && last_three_bit_value != 1) {
    printf("ERROR:invalid blocks bp:%p\n", bp);
  }
}

static void checkoverlap(void *bp, void *nxt) {
  // [begin,end), 左闭右开区间
  void *cur_end = FTRP(bp) + WSIZE;
  void *nxt_begin = HDRP(nxt);
  if (cur_end > nxt_begin) {
    printf("ERROR: blocks overlap cur_end: %p  nxt_begin:%p \n", cur_end,
           nxt_begin);
  }
}

/*
 * checkheap - Minimal check of the heap for consistency
 */
void checkheap(int verbose) {
  printf("in checkheap verbose:%d\n", verbose);
  char *bp = heap_listp;

  if (verbose) printf("Heap (%p):\n", heap_listp);

  // prologue block 双字大小(8字节),并且是allocate的状态。
  // 这里只检查了header,因为checkblock中检查了header和footer的一致性(指内容完全一致)
  if ((GET_SIZE(HDRP(heap_listp)) != DSIZE) || !GET_ALLOC(HDRP(heap_listp)))
    printf("Bad prologue header\n");
  checkblock(heap_listp);

  //连续空闲块的个数,遇到非free的清零,如果值大于等于2,说明有块躲过了合并
  int free_block_cnt = 0;

  // 遍历所有block. 除了epilogue
  // block,所有block不管是allocate还是free,size都是大于0的
  for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
    if (verbose) printblock(bp);
    checkblock(bp);

    // 检查是否有没合并的free block
    int alloc = GET_ALLOC(HDRP(bp));
    if (!alloc) {
      free_block_cnt++;
      if (free_block_cnt >= 2) {
        printf("contiguous free blocks that somehow escaped coalescing\n");
        if (verbose) {
          // 打印当前Block和上一个block
          printblock(bp);
          printblock(PREV_BLKP(bp));
        }
      }
    } else {
      free_block_cnt = 0;
    }

    // check (allocated) blocks overlap
    // 查看当前block的footer地址是否小于下一个block的header地址
    checkoverlap(bp, NEXT_BLKP(bp));
  }

  if (verbose) printblock(bp);
  if ((GET_SIZE(HDRP(bp)) != 0) || !(GET_ALLOC(HDRP(bp))))
    printf("Bad epilogue header\n");
}

Explicit Free Lists

隐式列表的坏处是。。每次allocate的时候,需要遍历全部block去找free block. 显然,我们可以维护一个free list的链表,使得每次allocate的时候,只需要遍历free block 结构如图:

9c05f9408157e3ac30f497772d0f436d.png

这里很巧妙的一点是,由于free block中的payload是没有被使用的,因此把上一个free block和下一个free block的地址都放在了当前free block的payload中,而没有单独维护一个数据结构。

需要注意的是,由于现在payload中存放了两个指针,因此目前一个block的最小size变成了16字节(heade,footer各4字节,payload要至少能放下两个指针,8字节,一共16字节)

还有几个值得一提的是 比如序言快的设计,是一个header紧跟着一个footer,没有payload

序言快很重要的一点是, HDRP和FTPR中间没有payload, 这其实意味着,可以把footer当成bp, 往前4个字节就是header 因此把free_list_star 放在序言快的footer的部分,作为一个结尾标志。判断条件可以统一成SIZE(HEAD(bp))= 0 这里是个挺巧妙的做法

还有就是一些链表操作,原来leetcode里面的链表题还是有实际用处的2333

// remove node in free list
// a->b->c ,remove b的做法是,将a->next指向c,c->prev 指向a
// 特殊情况: bp是free list的初始节点,此时直接调整free_list_start
static void remove_node_from_free_list(void *bp) {
  if (GET_PREV_PTR(bp)) {
    SET_NEXT_PTR(GET_PREV_PTR(bp), GET_NEXT_PTR(bp));
  } else {
    free_list_start = GET_NEXT_PTR(bp);
  }
  SET_PREV_PTR(GET_NEXT_PTR(bp), GET_PREV_PTR(bp));
}

// 向free list中插入node
// 这里涉及插入到哪里的策略
// 暂时使用头插法,也就是每次插入到free list的头部
// 对于 b->c,插入a,做法是
// a->next = free_list_start
// a->prev = null
// free_list_start->prev = a
// free_list_start = a

static void insert_node_in_free_list(void *bp) {
  SET_NEXT_PTR(bp, free_list_start);
  SET_PREV_PTR(free_list_start, bp);
  SET_PREV_PTR(bp, NULL);
  free_list_start = bp;
}

经验就是,由于涉及到比较底层的操作。。还挺难写的。。可以多定义一些宏来帮助开发。。(嗯。。也就core了100多次把。。

完整的代码在这里 111qqz's github

参考链接