[关闭]
@windmelon 2018-11-29T17:58:32.000000Z 字数 4768 阅读 4739

CSAPP:malloclab(一)

csapp实验

malloclab介绍

malloclab顾名思义就是要求自己实现c语言中的malloc函数，此外还有free和realloc函数
这个实验是csapp系列实验目前做到现在觉得最棘手的了=_=|||
可能是因为这部分上课没有认真听，参考了几个博客之后，终于理解了，先尝试完成一个最简单的隐式空闲链表+首次适配+原始realloc的版本，这个版本书上基本都给出了完整的代码，我们只需要实现find_fit()和place()即可

隐式空闲链表+首次适配+原始realloc

首先，先在mm.h中把需要的宏定义和函数声明加上

  1. #define WSIZE 4
  2. #define DSIZE 8
  3. #define CHUNKSIZE (1<<12)
  5. #define MAX(x,y) ((x)>(y)?(x):(y))
  7. #define PACK(size,alloc) ((size)|(alloc))
  9. #define GET(p)     (*(unsigned int *)(p))
  10. #define PUT(p,val) (*(unsigned int *)(p) = (val))
  12. #define GET_SIZE(p)  (GET(p) & ~0x7)
  13. #define GET_ALLOC(p) (GET(p) & 0x1)
  15. #define HDRP(bp) ((char *)(bp) - WSIZE)
  16. #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
  18. #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
  19. #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
  21. extern void *extend_heap(size_t words);
  22. extern void *coalesce(void *bp);
  23. extern void *find_fit(size_t size);
  24. extern void place(void *bp,size_t asize);
  25. extern int mm_init (void);
  26. extern void *mm_malloc (size_t size);
  27. extern void mm_free (void *ptr);
  28. extern void *mm_realloc(void *ptr, size_t size);

然后是mm.c里面各个函数的实现

不要忘记新建一个指向块首的指针，在遍历整个堆寻找合适块的时候要用到

  1. static char *heap_listp = 0;

mm_init()

image.png-95.8kB
以堆底为起始位置，新建四个WSIZE（4bytes or 32bits）大小的块
第一块什么都不放作为填充字
第二、三块分别作为序言块的头和脚
第四块作为结尾块
然后将指针后移两块，指向序言块脚部起始位置
随后调用extend_heap()，申请CHUNKSIZE大小的空间，以备用

  1. int mm_init(void)
  2. {
  3.     if((heap_listp = mem_sbrk(4*WSIZE))==(void *)-1){
  4.         return -1;
  5.     }
  6.     PUT(heap_listp,0);
  7.     PUT(heap_listp+(1*WSIZE),PACK(DSIZE,1));
  8.     PUT(heap_listp+(2*WSIZE),PACK(DSIZE,1));
  9.     PUT(heap_listp+(3*WSIZE),PACK(0,1));
  10.     heap_listp += (2*WSIZE);
  11.     if(extend_heap(CHUNKSIZE/WSIZE)==NULL){
  12.         return -1;
  13.     }
  14.     return 0;
  15. }

extend_heap()

此函数将堆扩容指定byte大小
如果指定words大小不为8的倍数则向上取整使得每次扩容都是八字节对齐
最后将头、脚内容补齐
并将下一个块置为结尾块
最后调用coalesce()函数堆bp进行合并操作后返回

  1. static void *extend_heap(size_t words){
  2.     char *bp;
  3.     size_t size;
  5.     size = (words%2) ? (words+1)*WSIZE : words*WSIZE;
  6.     if((long)(bp=mem_sbrk(size))==(void *)-1)
  7.         return NULL;
  9.     PUT(HDRP(bp),PACK(size,0));
  10.     PUT(FTRP(bp),PACK(size,0));
  11.     PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));
  13.     return coalesce(bp);
  14. }

mm_malloc()

此函数申请大小为size的空间
asize为对size进行8字节对齐检查后的大小
extendsize为取CHUNKSIZE和asize中较大者
先用find_fit()在现有的块中进行搜索，如果搜索到了，即用place()函数将asize大小的空间放到bp中（有可能全部分也可能分割成一个占用块和一个空闲块，所以不能粗暴的完全占用，要写一个place()函数来分配）
如果找不到合适块，就向堆申请新空间，新空间的大小为extendsize，然后再用place()函数放入

  1. void *mm_malloc(size_t size)
  2. {
  3.     size_t asize;
  4.     size_t extendsize;
  5.     char *bp;
  6.     if(size ==0) return NULL;
  8.     if(size <= DSIZE){
  9.         asize = 2*(DSIZE);
  10.     }else{
  11.         asize = (DSIZE)*((size+(DSIZE)+(DSIZE-1)) / (DSIZE));
  12.     }
  13.     if((bp = find_fit(asize))!= NULL){
  14.         place(bp,asize);
  15.         return bp;
  16.     }
  17.     extendsize = MAX(asize,CHUNKSIZE);
  18.     if((bp = extend_heap(extendsize/WSIZE))==NULL){
  19.         return NULL;
  20.     }
  21.     place(bp,asize);
  22.     return bp;
  23. }

mm_free()

此函数释放指针指向的占用块
很简单，将块的头尾块的alloc信息改为0
然后进行合并

  1. void mm_free(void *bp)
  2. {
  3.     if(bp == 0)
  4.     return;
  6.     size_t size = GET_SIZE(HDRP(bp));
  8.     PUT(HDRP(bp), PACK(size, 0));
  9.     PUT(FTRP(bp), PACK(size, 0));
  10.     coalesce(bp);
  11. }

coalesce（）

此函数将对传入的块指针进行前后检查
当然，传进来的是空闲块
如果前面块或者后面块同样为空闲块，就进行合并
说起来很简单，代码还是比较长，需要认真看看
首先获取前后块的空闲状态，然后进行条件判断
四种情况
1.前后都忙碌。2.前忙碌，后空闲。3.前空闲，后忙碌。4.前后都空闲
image.png-214.9kB

  1. static void *coalesce(void *bp){
  2.     size_t  prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
  3.     size_t  next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
  4.     size_t size = GET_SIZE(HDRP(bp));
  6.     if(prev_alloc && next_alloc) {
  7.         return bp;
  8.     }else if(prev_alloc && !next_alloc){
  9.             size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
  10.             PUT(HDRP(bp), PACK(size,0));
  11.             PUT(FTRP(bp), PACK(size,0));
  12.     }else if(!prev_alloc && next_alloc){
  13.         size += GET_SIZE(HDRP(PREV_BLKP(bp)));
  14.         PUT(FTRP(bp),PACK(size,0));
  15.         PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
  16.         bp = PREV_BLKP(bp);
  17.     }else {
  18.         size +=GET_SIZE(FTRP(NEXT_BLKP(bp)))+ GET_SIZE(HDRP(PREV_BLKP(bp)));
  19.         PUT(FTRP(NEXT_BLKP(bp)),PACK(size,0));
  20.         PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));
  21.         bp = PREV_BLKP(bp);
  22.     }
  23.     return bp;
  24. }

find_fit（）

此函数从头至尾遍历堆，找到合适大小的块则返回指向该块的指针（即头部块末尾）
找不到则返回NULL

  1. static void *find_fit(size_t size){
  2.     void *bp;
  3.     for(bp = heap_listp; GET_SIZE(HDRP(bp))>0; bp = NEXT_BLKP(bp)){
  4.         if(!GET_ALLOC(HDRP(bp)) && (size <= GET_SIZE(HDRP(bp)))){
  5.             return bp;
  6.         }
  7.     }
  8.     return NULL;
  9. }

place()

此函数将经过8字节对齐大小的空间放到指定的块中
如果分割后原块剩余大小大于2*DSIZE即16bytes
则进行分块
否则将整个块都占用

  1. static void place(void *bp,size_t asize){
  2.     size_t csize = GET_SIZE(HDRP(bp));
  3.     if((csize-asize)>=(2*DSIZE)){
  4.         PUT(HDRP(bp),PACK(asize,1));
  5.         PUT(FTRP(bp),PACK(asize,1));
  6.         bp = NEXT_BLKP(bp);
  7.         PUT(HDRP(bp),PACK(csize-asize,0));
  8.         PUT(FTRP(bp),PACK(csize-asize,0));
  9.     }else{
  10.         PUT(HDRP(bp),PACK(csize,1));
  11.         PUT(FTRP(bp),PACK(csize,1));
  12.     }
  13. }

mm_realloc()

此函数返回指向一个大小为size的区域指针，满足以下条件：
if ptr is NULL, the call is equivalent to mm_malloc(size);
if size is equal to zero, the call is equivalent to mm_free(ptr);
if ptr is not NULL：先按照size指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来ptr所指内存区域

  1. void *mm_realloc(void *ptr, size_t size)
  2. {
  3.     size_t oldsize;
  4.     void *newptr;
  6.     /* If size == 0 then this is just free, and we return NULL. */
  7.     if(size == 0) {
  8.     mm_free(ptr);
  9.     return 0;
  10.     }
  12.     /* If oldptr is NULL, then this is just malloc. */
  13.     if(ptr == NULL) {
  14.     return mm_malloc(size);
  15.     }
  17.     newptr = mm_malloc(size);
  19.     /* If realloc() fails the original block is left untouched  */
  20.     if(!newptr) {
  21.     return 0;
  22.     }
  24.     /* Copy the old data. */
  25.     oldsize = GET_SIZE(HDRP(ptr));
  26.     if(size < oldsize) oldsize = size;
  27.     memcpy(newptr, ptr, oldsize);
  29.     /* Free the old block. */
  30.     mm_free(ptr);
  32.     return newptr;
  33. }

至此，一个简单的隐式空闲链表+首次适配+原始realloc版本的malloclab就完成了

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注