CSAPP Lab07——Malloc Lab完成思路

等不到天黑

烟火不会太完美

回忆烧成灰

还是等不到结尾

——她说

完整代码见：CSAPP/malloclab-handout at main · SnowLegend-star/CSAPP (github.com)

Malloc Lab

按照惯例，我先是上来就把mm.c编译了一番，结果产生如下报错。搜索过后看样子应该是编译器的版本不匹配，得建立条软链接。

经过多番尝试，最后得到正确的链接形式是

“ln -s /usr/include/x86_64-linux-gnu/asm /usr/include/asm”

隐式空闲链表

这方法就是把书上的那几个函数搬过来就行，唯一需要自己动手的是realloc()函数。但是书上的那一大块宏定义属实是看得我两眼发昏。特别是NEXT_BLKP(bp)和PREV_BLKP(bp)这两个定义，直接把我绕晕了。

后来仔细分析了一番，发现最根本的原因是我把隐式空闲链表的头/尾块和内存块的头/尾部弄混了，导致每次分析堆内块的4byte头/尾部分的时候就会不自觉想到链表的头/尾部分。明白两者的不同之后，接下来分析宏定义等就显得直观明了了。

在排查bug的时候，没有实现把指针ptr定位到堆块的头部再进行指针操作确实是害苦了我。刚才就是一个困扰我很久的问题。

说完指针定位到头部的问题后，再来谈谈void *mm_realloc(void *ptr, size_t size)的实现框架。

1、ptr=NULL，size≠0：调用malloc()

2、ptr≠NULL，size=0：调用free()

3、ptr≠NULL，size≠0：调整size为asize

       3.1、asize=blocksize_Cur：直接分配

       3.2、asize<blocksize_Cur：调用place()把当前块进行分割

       3.3、asize>blocksize_Cur：当前块的大小不足以分配

3.3.1、next block空闲，且两个块的大小和blocksize_Sum>aszie：对下一块使用place()

3.3.2、next block已分配，或者两块大小和blocksize_Sum<aszie：调用find_fit()来寻找一个全新的块进行分配，而不考虑当前块和next block

       3.3.2.1、find_fit()找到了合适的块：调用place()进行分配

3.3.2.2、find_fit()未找到合适的块：先用extend_heap()来申请新的堆空间，再调用place()，最后把原来块的内容拷贝到新块里面，释放原来块的空间。

最后得到的测试结果如图。

//define function
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void place(void *bp,size_t asize);/* 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)))//basic constants and macros
#define WSIZE   4                         //字的大小和首部/脚部的大小
#define DSIZE   8                         //双字的大小
#define CHUNKSIZE (1<<12)              //扩展堆时的默认大小#define MAX(x,y)    ((x)>(y)?(x):(y))//pack a size and allocated bit into a word in header/footer 很绕啊
#define PACK(size ,alloc)   ((size)|(alloc))//read and write a word at address p
#define GET(p)      (*(unsigned int *)(p))
#define PUT(p,val)  (*(unsigned int *)(p)=(val))//read the size and allocated filds from address p
#define GET_SIZE(p)     (GET(p)&~0x7)
#define GET_ALLOC(p)    (GET(p)&0x1 )//given block ptr bp,compute address of its header and footer
#define HDRP(bp)    ((char *)(bp)-WSIZE)
#define FTRP(bp)    ((char*)(bp)+GET_SIZE(HDRP(bp))-DSIZE)  //没把bp定位到头部坏大事//given block ptr bp,computer address of next and previous blocks
#define NEXT_BLKP(bp)   ((char*)(bp)+GET_SIZE( (char*)(bp) - WSIZE) )
#define PREV_BLKP(bp)   ((char*)(bp)-GET_SIZE( (char*)(bp) - DSIZE) )static void *heap_listp;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));PUT(FTRP(bp),PACK(size,0));PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1)); //有点没看懂//如果前一个块空闲则合并return coalesce(bp);
}static void *find_fit(size_t asize){//h第一次适应算法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;
}static void place(void *bp,size_t asize){size_t cur_size=GET_SIZE(HDRP(bp));if((cur_size-asize)>=(2*WSIZE)){    //给16字节的头部、序言、结尾块腾位置PUT(HDRP(bp),PACK(asize,1));PUT(FTRP(bp),PACK(asize,1));bp=NEXT_BLKP(bp);               //移动到下一个块,就是分割完剩下的部分PUT(HDRP(bp),PACK(cur_size-asize,0));PUT(FTRP(bp),PACK(cur_size-asize,0));}else{                               //能用到place说明cur_size-asize>0  直接把这个给分配掉PUT(HDRP(bp),PACK(cur_size,1)); //因为剩下的空间也就0、1这两种，但是一个可用块最小为2WSIZEPUT(FTRP(bp),PACK(cur_size,1));}
}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){return bp;}else if(prev_alloc&&!next_alloc){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){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{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));}return bp;
}/* * mm_init - initialize the malloc package.*/
int mm_init(void)
{//开始创建初始的空堆,大小为4字if((heap_listp=mem_sbrk(4*WSIZE))==(void *) -1)return -1;// return 0;   //牛魔的，怎么这里有个returnPUT(heap_listp,0);                              //alignment paddingPUT(heap_listp+(1*WSIZE),PACK(DSIZE,1));        //prologue headerPUT(heap_listp+(2*WSIZE),PACK(DSIZE,1));        //prologue footerPUT(heap_listp+(3*WSIZE),PACK(0,1));            //epologue blockheap_listp+=(2*WSIZE);//增加堆的大小if(extend_heap(CHUNKSIZE/WSIZE)==NULL)return -1;return 0;
}/* * 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;   //adjusted block sizesize_t extendsize;  //如果大小超过堆的大小应该增加的总数char* bp;if(size==0)return NULL;//双字对齐if(size<=DSIZE)asize=2*DSIZE;elseasize=DSIZE*((size+(DSIZE)+(DSIZE-1))/DSIZE);   //加1向下舍入//从空闲链表里找合适的块进行分配if((bp=find_fit(asize))!=NULL){place(bp,asize);return bp;}//如果没有合适的空闲块，堆请求更大的空间extendsize=MAX(asize,CHUNKSIZE);if((bp=extend_heap(extendsize/WSIZE))==NULL)return NULL;place(bp,asize);return bp;}/** mm_free - Freeing a block does nothing.*/
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);
}/** mm_realloc - Implemented simply in terms of mm_malloc and mm_free*/
void *mm_realloc(void *ptr, size_t size)
{void *old_ptr=ptr,*next_ptr,*new_ptr;size_t asize;size_t extendsize;size_t blocksize_Cur,blocksize_Next,blocksize_Sum;    //当前块的大小，下一个块的大小if(ptr==NULL&&size!=0)return mm_malloc(size);if(ptr!=NULL&&size==0){mm_free(ptr); return NULL;       }//接下来就是指针不为空，且分配大小非0的正常情况了//双字对齐if(size<=DSIZE)asize=2*DSIZE;elseasize=DSIZE*((size+(DSIZE)+(DSIZE-1))/DSIZE);// blocksize_Cur=GET_SIZE(ptr);    //ptr得定位到头部☆☆☆blocksize_Cur=GET_SIZE(HDRP(ptr));if(asize==blocksize_Cur){return ptr;        }else if(asize<blocksize_Cur){       //当前块的大小>要求分配的空间大小place(ptr,asize);return ptr;}else{                               //当前块的大小<要求分配的空间大小next_ptr=NEXT_BLKP(ptr);blocksize_Next=GET_SIZE(HDRP(next_ptr));blocksize_Sum=blocksize_Cur+blocksize_Next;if(GET_ALLOC(HDRP(next_ptr))==0&&blocksize_Sum>=asize){  //当前块大小+下一块大小>asizePUT(HDRP(ptr),PACK(blocksize_Sum,0));           //把当前块和下一块合并place(ptr,asize);return ptr;}else{new_ptr=find_fit(asize);if(new_ptr==NULL){      //如果当前链表找不到合适的块，则申请额外的空间extendsize=MAX(CHUNKSIZE,asize);if((new_ptr=extend_heap(extendsize/WSIZE))==NULL)return NULL;}place(new_ptr,asize);memcpy(new_ptr,old_ptr,blocksize_Cur);mm_free(old_ptr);return new_ptr;}}
}

显式空闲链表

按照书上思路来写就行

Tip：有char **p1和int **p2，那p1==p2吗？

/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8                     //对齐8个字节(2个字)/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t))) //头部、脚部、两指针、8字节数据//basic constants and macros
#define WSIZE   4                         //字的大小和首部/脚部的大小
#define DSIZE   8                         //双字的大小
#define CHUNKSIZE   (1<<12)              //扩展堆时的默认大小
#define MINBLOCK    (DSIZE+2*WSIZE+2*WSIZE)#define MAX(x,y)    ((x)>(y)?(x):(y))//pack a size and allocated bit into a word in header/footer 很绕啊
#define PACK(size ,alloc)   ((size)|(alloc))//read and write a word at address p
#define GET(p)      (*(unsigned int *)(p))
#define PUT(p,val)  (*(unsigned int *)(p)=(val))
#define GETADDR(p) (*(unsigned int **)(p)) //读地址p处的一个指针
#define PUTADDR(p,addr) (*(unsigned int **)(p)=(unsigned int *)(addr)) //在地址p处写的指针//read the size and allocated filds from address p
#define GET_SIZE(p)     (GET(p)&~0x7)
#define GET_ALLOC(p)    (GET(p)&0x1 )//given block ptr bp,compute address of its header and footer
#define HDRP(bp)    ((char *)(bp)-WSIZE)
#define FTRP(bp)    ((char*)(bp)+GET_SIZE(HDRP(bp))-DSIZE)  //没把bp定位到头部坏大事//given block ptr bp,computer address of next and previous blocks
#define NEXT_BLKP(bp)   ((char*)(bp)+GET_SIZE( (char*)(bp) - WSIZE) )
#define PREV_BLKP(bp)   ((char*)(bp)-GET_SIZE( (char*)(bp) - DSIZE) )//链表特有的指针
#define PRED_POINTER(bp)    (bp)    //指向父指针的指针
#define SUCC_POINTER(bp)    ((char*)(bp)+WSIZE) //指向后继的指针static void *heap_listp;
static void *head_free;//define function
static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *find_fit(size_t asize);
static void place(void *bp,size_t asize);//链表操作
static void insert_freelist(void *bp);
static void remove_freelist(void *bp);
static void place_freelist(void *bp);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));PUT(FTRP(bp),PACK(size,0));PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1)); //有点没看懂//如果前一个块空闲则合并return coalesce(bp);
}static void *find_fit(size_t asize){//h第一次适应算法void *bp;for(bp=GETADDR(head_free);bp!=NULL;bp=GETADDR(SUCC_POINTER(bp))){ //遍历空闲链表if((asize<=GET_SIZE(HDRP(bp))))   //这个块没被分配且容量合适return bp;}return NULL;
}static void place(void *bp,size_t asize){size_t cur_size=GET_SIZE(HDRP(bp));void *next_bp;if((cur_size-asize)>=(MINBLOCK)){    //最小块的大小为24B，这里包括了有效载荷的部分PUT(HDRP(bp),PACK(asize,1));PUT(FTRP(bp),PACK(asize,1));next_bp=NEXT_BLKP(bp);               //移动到下一个块,就是分割完剩下的部分PUT(HDRP(next_bp),PACK(cur_size-asize,0));PUT(FTRP(next_bp),PACK(cur_size-asize,0));place_freelist(bp);}else{                               //能用到place说明cur_size-asize>0  直接把这个给分配掉PUT(HDRP(bp),PACK(cur_size,1)); //因为剩下的空间也就0、1这两种，但是一个可用块最小为2WSIZEPUT(FTRP(bp),PACK(cur_size,1));remove_freelist(bp);}
}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));char *pre_block,*next_block;if(prev_alloc&&next_alloc){insert_freelist(bp);return bp;}else if(prev_alloc&&!next_alloc){   //合并下一块size+=GET_SIZE(HDRP(NEXT_BLKP(bp)));next_block=NEXT_BLKP(bp);   remove_freelist(next_block);insert_freelist(bp);}else if(!prev_alloc&&next_alloc){   //合并前一块size+=GET_SIZE(HDRP(PREV_BLKP(bp)));bp=PREV_BLKP(bp);remove_freelist(bp);insert_freelist(bp);}else{   //前后块都合并size+=GET_SIZE(HDRP(PREV_BLKP(bp)))+GET_SIZE(FTRP(NEXT_BLKP(bp)));pre_block=PREV_BLKP(bp);next_block=NEXT_BLKP(bp);bp=PREV_BLKP(bp);remove_freelist(pre_block);remove_freelist(next_block);insert_freelist(bp);}PUT(HDRP(bp),PACK(size,0));PUT(FTRP(bp),PACK(size,0));return bp;
}//使用头插法，将空闲块插入空闲链表中
static void insert_freelist(void *bp){  //LIFO，先进后出if(GETADDR(head_free)==NULL){PUTADDR(SUCC_POINTER(bp),NULL);PUTADDR(PRED_POINTER(bp),head_free);PUTADDR(head_free,bp);}else{void *tmp;tmp=GETADDR(head_free);PUTADDR(SUCC_POINTER(bp),tmp);PUTADDR(PRED_POINTER(bp),head_free);PUTADDR(head_free,bp);PUTADDR(PRED_POINTER(tmp),bp);tmp=NULL;}
}//将bp指向的空闲块从空闲链表中移除
static void remove_freelist(void *bp){void *pred_ptr,*succ_ptr;pred_ptr=GETADDR(PRED_POINTER(bp));succ_ptr=GETADDR(SUCC_POINTER(bp));//处理前驱节点if(pred_ptr==head_free){PUTADDR(head_free,succ_ptr);}else{PUTADDR(SUCC_POINTER(pred_ptr),succ_ptr);}//处理后继节点if(succ_ptr!=NULL){PUTADDR(PRED_POINTER(succ_ptr),pred_ptr);}
}//对空闲链表中的空闲块进行分割
static void place_freelist(void *bp){void *pred_ptr,*succ_ptr,*next_bp;//储存前后结点的地址pred_ptr=GETADDR(PRED_POINTER(bp));succ_ptr=GETADDR(SUCC_POINTER(bp));next_bp=NEXT_BLKP(bp);//处理新的bp，进行前后链接PUTADDR(PRED_POINTER(next_bp),pred_ptr);PUTADDR(SUCC_POINTER(next_bp),succ_ptr);//处理前序节点，针对head_free是前序节点的特殊处理if(pred_ptr==head_free){PUTADDR(head_free,next_bp);}else{PUTADDR(SUCC_POINTER(pred_ptr),next_bp);}//处理后序节点if(succ_ptr!=NULL){PUTADDR(PRED_POINTER(succ_ptr),next_bp);}
}
/* * mm_init - initialize the malloc package.*/
//设立序言块、结尾块，以及序言块前的对齐块（4B），总共需要4个4B的空间
int mm_init(void)
{//开始创建初始的空堆,大小为4字if((heap_listp=mem_sbrk(4*WSIZE))==(void *) -1)return -1;PUTADDR(heap_listp,NULL);                       //堆起始位置的对齐块，是bp对齐8字节// PUT(heap_listp,0);                              //alignment paddingPUT(heap_listp+(1*WSIZE),PACK(DSIZE,1));        //prologue headerPUT(heap_listp+(2*WSIZE),PACK(DSIZE,1));        //prologue footerPUT(heap_listp+(3*WSIZE),PACK(0,1));            //epologue block 存疑head_free=heap_listp;PUTADDR(head_free,NULL);heap_listp+=(2*WSIZE);//增加堆的大小if(extend_heap(CHUNKSIZE/WSIZE)==NULL)return -1;return 0;
}/* * 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;   //adjusted block sizesize_t extendsize;  //如果大小超过堆的大小应该增加的总数char* bp;if(size==0)return NULL;//双字对齐if(size<=DSIZE)asize=2*DSIZE;elseasize=DSIZE*((size+(DSIZE)+(DSIZE-1))/DSIZE);   //加1向下舍入//从空闲链表里找合适的块进行分配if((bp=find_fit(asize))!=NULL){place(bp,asize);return bp;}//如果没有合适的空闲块，堆请求更大的空间extendsize=MAX(asize,CHUNKSIZE);if((bp=extend_heap(extendsize/WSIZE))==NULL)return NULL;place(bp,asize);return bp;}/** mm_free - Freeing a block does nothing.*/
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);
}/** mm_realloc - Implemented simply in terms of mm_malloc and mm_free*/
void *mm_realloc(void *ptr, size_t size)
{void *old_ptr=ptr,*new_ptr;size_t asize;size_t extendsize;size_t blocksize_Cur;    //当前块的大小，下一个块的大小if(ptr==NULL&&size!=0)return mm_malloc(size);if(ptr!=NULL&&size==0){mm_free(ptr); return NULL;       }//接下来就是指针不为空，且分配大小非0的正常情况了//双字对齐if(size<=DSIZE)asize=2*DSIZE;elseasize=DSIZE*((size+(DSIZE)+(DSIZE-1))/DSIZE);// blocksize_Cur=GET_SIZE(ptr);    //ptr得定位到头部☆☆☆blocksize_Cur=GET_SIZE(HDRP(ptr));if(asize==blocksize_Cur){return ptr;        }else if(asize<blocksize_Cur){       //当前块的大小>要求分配的空间大小if(blocksize_Cur-asize>=MINBLOCK)place(ptr,asize);return ptr;}else{                               //当前块的大小<要求分配的空间大new_ptr=find_fit(asize);if(new_ptr==NULL){      //如果当前链表找不到合适的块，则申请额外的空间extendsize=MAX(CHUNKSIZE,asize);if((new_ptr=extend_heap(extendsize/WSIZE))==NULL)return NULL;}place(new_ptr,asize);memcpy(new_ptr,old_ptr,blocksize_Cur-2*WSIZE);mm_free(old_ptr);return new_ptr;}
}

分离空闲链表

对于显式空闲链表，判断节点bp的前驱是否是头结点相当简单，如下

但是对于分离空闲链表来说，就显得比较繁琐了。按照上面的思路，我们得先用一个大循环来遍历24条链表的各个头结点，然后再用上述式子。不如把这个循环遍历做成一个单独的函数，以此来判断前驱是否头结点的问题。

if(isSegList(pred_ptr)){    //如果前驱是头结点

汗流浃背了，代码出了个bug。

然后是调试环节。

我先是一直在那输入“gdb mm”，结果代码在gdb模式下run起来都有问题，让我心生怀疑可能是调试错了文件，最后才发现pdf上写着调试应该是“gdb mdriver”，白忙活一场。由于默认调试的执行文件是“short1-bal.rep”，想要调试其他文件就得改config.h，但是我发现无论怎么修改config.h，都会报下面的错误。这也是浪费最多时间的一部分。