CSAPP实验——malloc lab

官网

http://csapp.cs.cmu.edu/3e/labs.html

Students implement simple logical, two’s complement, and floating point functions, but using a highly restricted subset of C. For example, they might be asked to compute the absolute value of a number using only bit-level operations and straightline code. This lab helps students understand the bit-level representations of C data types and the bit-level behavior of the operations on data.

参考

[读书笔记]CSAPP：MallocLab

CSAPP: Malloc lab

实验要求

在mm.c里完善一个自己的动态分配器。

int mm_init(void);: 调用其他几个函数前，调用mm_init进行必要的初始化。初始化发生错误时，应返回-1，正常则返回0。
void *mm_malloc(size_t size);: 返回一个指针，指向一个至少size字节的已分配块的有效载荷。整个分配块应位于堆区域内，且不与任何其他分配块重叠。该函数应和libc中的malloc一样，总是返回 8 字节对齐的指针。
void mm_free(void *ptr);: 释放指针ptr指向的块，不返回任何值。只有指针ptr是由mm_malloc或者mm_realloc先前返回的时候，该函数会保证正常工作。
void *mm_realloc(void *ptr, size_t size);: 返回值同mm_malloc，但是有以下限制：
- 如果ptr为空，等同于调用mm_malloc(size)
- 如果size=0，等同于调用mm free(ptr)
- 否则，指针ptr必须是由mm_malloc或者mm_realloc先前返回的。该函数修改该块的大小为size，然后返回新块的地址。新块的地址是否和旧块相同，取决于旧块的内部碎片情况和新块所请求的大小。
- 如果是”压缩“，旧块的部分内容扔保留。如果是”扩展“，旧块的内容保留，扩展区域为非初始化的。

辅助函数

可以使用memlib.c里的函数。

void *mem sbrk(int incr): Expands the heap by incr bytes, where incr is a positive non-zero integer and returns a generic pointer to the first byte of the newly allocated heap area. The semantics are identical to the Unix sbrk function, except that mem sbrk accepts only a positive non-zero integer argument.
void *mem heap lo(void): Returns a generic pointer to the first byte in the heap.
void *mem heap hi(void): Returns a generic pointer to the last byte in the heap.
size t mem heapsize(void): Returns the current size of the heap in bytes.
size t mem pagesize(void): Returns the system’s page size in bytes (4K on Linux systems).

评分

调用./mdriver -f short1-bal.rep -V来查看单个文件的测试结果。该课程的其他测试数据可以从这里下载，得到一个trace文件夹，然后调用./mdriver -t ./trace -V来查看测试结果。

思路

分离空闲链表：segregated free list中按大小类分类，并且将该list表放在heap的头部，通过序言块将它与数据隔离。在每一个大小类中，空闲块按照size由小到大排序。
立即合并：free()后对空闲块立即合并。
最佳适配：因为同一大小类中空闲块由小到大排序，所以查找是第一个合适的就是最适配的。
改进的realloc：对于请求“扩展”这种情况，运用类似coalesce中的方法，先去检查前后是否有空闲块，并是否满足前后空闲块和当前已分配的空闲块size相加大于newsize，如果是则合并，不需要再重新请求空闲块。如果不行，则需要重新mm_malloc一块新的空间。

块的数据结构

空闲块使用两个字的空间分别记录了前驱和后继的空闲块，这样，所有空闲块就可以显式地链接起来，就能轻松地直接遍历所有的空闲块了。

宏和全局变量

定义如下宏和全局变量：

/* 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           /*Double word size*/
#define CHUNKSIZE (1<<12) /*the page size in bytes is 4K*/

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

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

#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 PREV_LINKNODE_RP(bp) ((char*)(bp))
#define NEXT_LINKNODE_RP(bp) ((char*)(bp)+WSIZE)

#define NEXT_BLKP(bp)   ((char *)(bp)+GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp)   ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE)))

static char *heap_listp = NULL;
static char *block_list_start = NULL;

PREV_LINKNODE_RP就是前文所提到的空闲块中的前驱指针，NEXT_LINKNODE_RP同理。bp指向的是块header下一个字的位置。

heap_listp指向序言块的有效载荷，有如下结构：

block_list_start则是指向第一个空闲链表的位置。

空闲链表

一共有10个空闲链表，不需要记录小于16Bytes的块，因为空闲块最小为16Bytes。空闲链表内的空闲块大小范围分别如下。

{0-32},{33-64},{65-128},{129-256},{257-512},{513-1024},{1025-2048},{2049-3072}，{3073-4096}，{4097-inf}

ins_block是将一个空闲块插入对应的空闲链表中，注意要保证各块大小非递减，便于进行最佳适配。

void ins_block(char *p) {
   char *root = find_list_root(GET_SIZE(HDRP(p)));
   char *prevp = root;
   char *nextp = GET(root);

   while (nextp != NULL) { // prevp为小于当前块大小的最后一个元素
      if (GET_SIZE(HDRP(nextp)) >= GET_SIZE(HDRP(p))) break;
      prevp = nextp;
      nextp = GET(NEXT_LINKNODE_RP(nextp));
   }
   if (prevp == root) { // 空链表，新结点作为根节点
      PUT(root, p);
      PUT(NEXT_LINKNODE_RP(p), nextp);
      PUT(PREV_LINKNODE_RP(p), NULL);
      if (nextp != NULL) PUT(PREV_LINKNODE_RP(nextp), p);
   } else { // 插入到prevp结点之后
      PUT(NEXT_LINKNODE_RP(prevp), p);
      PUT(PREV_LINKNODE_RP(p), prevp);
      PUT(NEXT_LINKNODE_RP(p), nextp);
      if (nextp != NULL) PUT(PREV_LINKNODE_RP(nextp), p);
   }
}

与其相对应的，del_block把某个块从相应链表中删除。

void del_block(char *p) {
   char *root = find_list_root(GET_SIZE(HDRP(p)));
   char *prevp = GET(PREV_LINKNODE_RP(p));
   char *nextp = GET(NEXT_LINKNODE_RP(p));

   if (prevp == NULL && nextp == NULL) //无先驱无后继
   {
      PUT(root, 0);
   } else if (prevp != NULL && nextp == NULL) //有先驱无后继
   {
      PUT(NEXT_LINKNODE_RP(prevp), nextp);
   } else if (prevp == NULL && nextp != NULL) //无先驱有后继
   {
      PUT(PREV_LINKNODE_RP(nextp), 0);
      PUT(root, nextp);
   } else if (prevp != NULL && nextp != NULL) //有先驱有后继
   {
      PUT(PREV_LINKNODE_RP(nextp), prevp);
      PUT(NEXT_LINKNODE_RP(prevp), nextp);
   }

   PUT(NEXT_LINKNODE_RP(p), NULL);
   PUT(PREV_LINKNODE_RP(p), NULL);
}

find_list_root是计算某个大小为size的空闲块应该对应于哪个空闲链表，返回对应空闲链表的首地址。

char *find_list_root(size_t size) {
   int i;
   // 不需要记录小于16bytes的块，因为空闲块最小为16bytes。
   if (size <= 32) i = 0;
   else if (size <= 64) i = 1;
   else if (size <= 128) i = 2;
   else if (size <= 256) i = 3;
   else if (size <= 512) i = 4;
   else if (size <= 1024) i = 5;
   else if (size <= 2048) i = 6;
   else if (size <= 3072) i = 7;
   else if (size <= 4096) i = 8;
   else i = 9;
   /*find the index of bin which will put this block */
   return block_list_start + i * WSIZE;
}

mm_init

/*
 * mm_init - initialize the malloc package.
 */
int mm_init(void) {
   int ind;

   if ((heap_listp = mem_sbrk(14 * WSIZE)) == (void *) -1) return -1; // 申请14字空间

   for (ind = 0; ind < 10; ind++) PUT(heap_listp + ind * WSIZE, 0); //block list
   PUT(heap_listp + 10 * WSIZE, 0);   /*Alignment padding*/
   PUT(heap_listp + 11 * WSIZE, PACK(DSIZE, 1)); /*Prologue header*/
   PUT(heap_listp + 12 * WSIZE, PACK(DSIZE, 1)); /*Prologue footer*/
   PUT(heap_listp + 13 * WSIZE, PACK(0, 1)); /*Epilogue header*/

   block_list_start = heap_listp;
   heap_listp += 12 * WSIZE; /*指向序言块*/

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

和CSAPP书上的例程没有太大区别，主要是加入了block list，放在序言块之前。注意申请的堆大小要保持双字对齐，使用padding块同时还可以将序言块和block list部分隔开。heap_listp仍是指向序言块的有效载荷。涉及到的extend_heap和coalesce函数如下。主要注意链表和NEXT_LINKNODE_RP等字段的维护。

static void *extend_heap(size_t words) {
   char *bp;
   size_t size;
   // 分配空间双字对齐
   size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;

   if ((bp = mem_sbrk(size)) == (void *) -1) return NULL;

   PUT(HDRP(bp), PACK(size, 0));
   PUT(FTRP(bp), PACK(size, 0));
   PUT(NEXT_LINKNODE_RP(bp), NULL);
   PUT(PREV_LINKNODE_RP(bp), NULL);

   PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /*New Epilogue header*/

   return coalesce(bp);
}

/*coalesce the empty block*/
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));

   /*coalesce the block and change the point*/
   /*prev_alloc && next_alloc不做任何合并*/
   if (prev_alloc && !next_alloc) {
      size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
      del_block(NEXT_BLKP(bp));
      PUT(HDRP(bp), PACK(size, 0));
      PUT(FTRP(bp), PACK(size, 0));
   } else if (!prev_alloc && next_alloc) {
      size += GET_SIZE(HDRP(PREV_BLKP(bp)));
      del_block(PREV_BLKP(bp));
      PUT(FTRP(bp), PACK(size, 0));
      PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
      bp = PREV_BLKP(bp);
   } else if (!prev_alloc) {
      size += GET_SIZE(FTRP(NEXT_BLKP(bp))) + GET_SIZE(HDRP(PREV_BLKP(bp)));
      del_block(PREV_BLKP(bp));
      del_block(NEXT_BLKP(bp));
      PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
      PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
      bp = PREV_BLKP(bp);
   }
   ins_block(bp);
   return bp;
}

mm_malloc

/*
 * 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) {
   size_t asize;
   size_t extendsize;
   char *bp;

   if (size == 0) return NULL;

   asize = size <= DSIZE ? 2 * DSIZE : DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

   if ((bp = find_fit(asize)) == NULL) { // 最优适配失败, apply new block
      extendsize = MAX(asize, CHUNKSIZE);
      if ((bp = extend_heap(extendsize / WSIZE)) == NULL) {
         return NULL;
      }
   }
   place(bp, asize);
   return bp;
}

static void place(void *bp, size_t asize) {
    size_t csize = GET_SIZE(HDRP(bp));
    /*remove from empty_list*/
    del_block(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));
        PUT(NEXT_LINKNODE_RP(bp), 0);
        PUT(PREV_LINKNODE_RP(bp), 0);
        coalesce(bp);
    } else {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

mm_free

/*
 * mm_free - Freeing a block does nothing.
 */
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));
   PUT(NEXT_LINKNODE_RP(ptr), NULL);
   PUT(PREV_LINKNODE_RP(ptr), NULL);
   coalesce(ptr);
}

也是要注意NEXT_LINKNODE_RP等字段的维护。采用的是立即合并策略，释放后就立即尝试与前后空闲块进行合并。

重点：mm_realloc

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size) {
   size_t oldsize = GET_SIZE(HDRP(ptr));
   void *newptr;
   size_t asize;

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

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

   asize = size <= DSIZE ? 2 * DSIZE : DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);

   if (oldsize == asize) return ptr;
   if (oldsize < asize) {
      //改进，直接合并再扩展
      int isnextFree;
      char *bp = realloc_coalesce(ptr, asize, &isnextFree);
      if (isnextFree == 1) { /*next block is free*/
         realloc_place(bp, asize);
         return bp;
      } else if (isnextFree == 0 && bp != ptr) {
         /*previous block is free, move the point to new address,and move the payload*/
         memcpy(bp, ptr, size);
         realloc_place(bp, asize);
         return bp;
      } else {
         /*realloc_coalesce is fail*/
         newptr = mm_malloc(size);
         memcpy(newptr, ptr, size);
         mm_free(ptr);
         return newptr;
      }
   } else {
      realloc_place(ptr, asize);
      return ptr;
   }
}

根据实验要求，在需要重新分配一块更大的内存块时，首先判断前后是否为空闲块，可以就地分配。相应的place和coalesce函数也要作出修改。

static void realloc_place(void *bp, size_t asize) {
   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));
      PUT(NEXT_LINKNODE_RP(bp), 0);
      PUT(PREV_LINKNODE_RP(bp), 0);
      coalesce(bp);
   } else {
      PUT(HDRP(bp), PACK(csize, 1));
      PUT(FTRP(bp), PACK(csize, 1));
   }
}

static void *realloc_coalesce(void *bp, size_t newSize, int *isNextFree) {
   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));
   *isNextFree = 0;

   /*prev_alloc && next_alloc不做任何合并*/
   if (prev_alloc && !next_alloc) {
      size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
      if (size >= newSize) {
         del_block(NEXT_BLKP(bp));
         PUT(HDRP(bp), PACK(size, 1));
         PUT(FTRP(bp), PACK(size, 1));
         *isNextFree = 1;
         return bp;
      }
   } else if (!prev_alloc && next_alloc) {
      size += GET_SIZE(HDRP(PREV_BLKP(bp)));
      if (size >= newSize) {
         del_block(PREV_BLKP(bp));
         PUT(FTRP(bp), PACK(size, 1));
         PUT(HDRP(PREV_BLKP(bp)), PACK(size, 1));
         bp = PREV_BLKP(bp);
         return bp;
      }
   } else if (!prev_alloc) {
      size += GET_SIZE(FTRP(NEXT_BLKP(bp))) + GET_SIZE(HDRP(PREV_BLKP(bp)));
      if (size >= newSize) {
         del_block(PREV_BLKP(bp));
         del_block(NEXT_BLKP(bp));
         PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 1));
         PUT(HDRP(PREV_BLKP(bp)), PACK(size, 1));
         bp = PREV_BLKP(bp);
      }
   }
   return bp;
}