谷歌上怎样做网站,个人主页网站,南昌行业网站建设,一个人看的片免费高清大全等不到天黑 烟火不会太完美 回忆烧成灰 还是等不到结尾 ——她说 完整代码见#xff1a;CSAPP/malloclab-handout at main SnowLegend-star/CSAPP (github.com) Malloc Lab
按照惯例#xff0c;我先是上来就把mm.c编译了一番#xff0c;结果产生如下报错。搜索过后看样子应… 等不到天黑 烟火不会太完美 回忆烧成灰 还是等不到结尾 ——她说 完整代码见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、ptrNULLsize≠0调用malloc() 2、ptr≠NULLsize0调用free() 3、ptr≠NULLsize≠0调整size为asize 3.1、asizeblocksize_Cur直接分配 3.2、asizeblocksize_Cur调用place()把当前块进行分割 3.3、asizeblocksize_Cur当前块的大小不足以分配 3.3.1、next block空闲且两个块的大小和blocksize_Sumaszie对下一块使用place() 3.3.2、next block已分配或者两块大小和blocksize_Sumaszie调用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 (112) //扩展堆时的默认大小#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)?(words1)*WSIZE:words*WSIZE;if((long)(bpmem_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(bpheap_listp;GET_SIZE(HDRP(bp))0;bpNEXT_BLKP(bp)){if(!GET_ALLOC(HDRP(bp))(asizeGET_SIZE(HDRP(bp)))) //这个块没被分配且容量合适return bp;}return NULL;
}static void place(void *bp,size_t asize){size_t cur_sizeGET_SIZE(HDRP(bp));if((cur_size-asize)(2*WSIZE)){ //给16字节的头部、序言、结尾块腾位置PUT(HDRP(bp),PACK(asize,1));PUT(FTRP(bp),PACK(asize,1));bpNEXT_BLKP(bp); //移动到下一个块,就是分割完剩下的部分PUT(HDRP(bp),PACK(cur_size-asize,0));PUT(FTRP(bp),PACK(cur_size-asize,0));}else{ //能用到place说明cur_size-asize0 直接把这个给分配掉PUT(HDRP(bp),PACK(cur_size,1)); //因为剩下的空间也就0、1这两种但是一个可用块最小为2WSIZEPUT(FTRP(bp),PACK(cur_size,1));}
}static void *coalesce(void *bp){size_t prev_allocGET_ALLOC(FTRP(PREV_BLKP(bp)));size_t next_allocGET_ALLOC(HDRP(NEXT_BLKP(bp)));size_t sizeGET_SIZE(HDRP(bp));if(prev_allocnext_alloc){return bp;}else if(prev_alloc!next_alloc){sizeGET_SIZE(HDRP(NEXT_BLKP(bp)));PUT(HDRP(bp),PACK(size,0));PUT(FTRP(bp),PACK(size,0));}else if(!prev_allocnext_alloc){sizeGET_SIZE(HDRP(PREV_BLKP(bp)));PUT(FTRP(bp),PACK(size,0));PUT(HDRP(PREV_BLKP(bp)),PACK(size,0));bpPREV_BLKP(bp);}else{sizeGET_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_listpmem_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(size0)return NULL;//双字对齐if(sizeDSIZE)asize2*DSIZE;elseasizeDSIZE*((size(DSIZE)(DSIZE-1))/DSIZE); //加1向下舍入//从空闲链表里找合适的块进行分配if((bpfind_fit(asize))!NULL){place(bp,asize);return bp;}//如果没有合适的空闲块堆请求更大的空间extendsizeMAX(asize,CHUNKSIZE);if((bpextend_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 sizeGET_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_ptrptr,*next_ptr,*new_ptr;size_t asize;size_t extendsize;size_t blocksize_Cur,blocksize_Next,blocksize_Sum; //当前块的大小下一个块的大小if(ptrNULLsize!0)return mm_malloc(size);if(ptr!NULLsize0){mm_free(ptr); return NULL; }//接下来就是指针不为空且分配大小非0的正常情况了//双字对齐if(sizeDSIZE)asize2*DSIZE;elseasizeDSIZE*((size(DSIZE)(DSIZE-1))/DSIZE);// blocksize_CurGET_SIZE(ptr); //ptr得定位到头部☆☆☆blocksize_CurGET_SIZE(HDRP(ptr));if(asizeblocksize_Cur){return ptr; }else if(asizeblocksize_Cur){ //当前块的大小要求分配的空间大小place(ptr,asize);return ptr;}else{ //当前块的大小要求分配的空间大小next_ptrNEXT_BLKP(ptr);blocksize_NextGET_SIZE(HDRP(next_ptr));blocksize_Sumblocksize_Curblocksize_Next;if(GET_ALLOC(HDRP(next_ptr))0blocksize_Sumasize){ //当前块大小下一块大小asizePUT(HDRP(ptr),PACK(blocksize_Sum,0)); //把当前块和下一块合并place(ptr,asize);return ptr;}else{new_ptrfind_fit(asize);if(new_ptrNULL){ //如果当前链表找不到合适的块则申请额外的空间extendsizeMAX(CHUNKSIZE,asize);if((new_ptrextend_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那p1p2吗 /* 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 (112) //扩展堆时的默认大小
#define MINBLOCK (DSIZE2*WSIZE2*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)?(words1)*WSIZE:words*WSIZE;if((long)(bpmem_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(bpGETADDR(head_free);bp!NULL;bpGETADDR(SUCC_POINTER(bp))){ //遍历空闲链表if((asizeGET_SIZE(HDRP(bp)))) //这个块没被分配且容量合适return bp;}return NULL;
}static void place(void *bp,size_t asize){size_t cur_sizeGET_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_bpNEXT_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-asize0 直接把这个给分配掉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_allocGET_ALLOC(FTRP(PREV_BLKP(bp)));size_t next_allocGET_ALLOC(HDRP(NEXT_BLKP(bp)));size_t sizeGET_SIZE(HDRP(bp));char *pre_block,*next_block;if(prev_allocnext_alloc){insert_freelist(bp);return bp;}else if(prev_alloc!next_alloc){ //合并下一块sizeGET_SIZE(HDRP(NEXT_BLKP(bp)));next_blockNEXT_BLKP(bp); remove_freelist(next_block);insert_freelist(bp);}else if(!prev_allocnext_alloc){ //合并前一块sizeGET_SIZE(HDRP(PREV_BLKP(bp)));bpPREV_BLKP(bp);remove_freelist(bp);insert_freelist(bp);}else{ //前后块都合并sizeGET_SIZE(HDRP(PREV_BLKP(bp)))GET_SIZE(FTRP(NEXT_BLKP(bp)));pre_blockPREV_BLKP(bp);next_blockNEXT_BLKP(bp);bpPREV_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;tmpGETADDR(head_free);PUTADDR(SUCC_POINTER(bp),tmp);PUTADDR(PRED_POINTER(bp),head_free);PUTADDR(head_free,bp);PUTADDR(PRED_POINTER(tmp),bp);tmpNULL;}
}//将bp指向的空闲块从空闲链表中移除
static void remove_freelist(void *bp){void *pred_ptr,*succ_ptr;pred_ptrGETADDR(PRED_POINTER(bp));succ_ptrGETADDR(SUCC_POINTER(bp));//处理前驱节点if(pred_ptrhead_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_ptrGETADDR(PRED_POINTER(bp));succ_ptrGETADDR(SUCC_POINTER(bp));next_bpNEXT_BLKP(bp);//处理新的bp进行前后链接PUTADDR(PRED_POINTER(next_bp),pred_ptr);PUTADDR(SUCC_POINTER(next_bp),succ_ptr);//处理前序节点针对head_free是前序节点的特殊处理if(pred_ptrhead_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_listpmem_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_freeheap_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(size0)return NULL;//双字对齐if(sizeDSIZE)asize2*DSIZE;elseasizeDSIZE*((size(DSIZE)(DSIZE-1))/DSIZE); //加1向下舍入//从空闲链表里找合适的块进行分配if((bpfind_fit(asize))!NULL){place(bp,asize);return bp;}//如果没有合适的空闲块堆请求更大的空间extendsizeMAX(asize,CHUNKSIZE);if((bpextend_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 sizeGET_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_ptrptr,*new_ptr;size_t asize;size_t extendsize;size_t blocksize_Cur; //当前块的大小下一个块的大小if(ptrNULLsize!0)return mm_malloc(size);if(ptr!NULLsize0){mm_free(ptr); return NULL; }//接下来就是指针不为空且分配大小非0的正常情况了//双字对齐if(sizeDSIZE)asize2*DSIZE;elseasizeDSIZE*((size(DSIZE)(DSIZE-1))/DSIZE);// blocksize_CurGET_SIZE(ptr); //ptr得定位到头部☆☆☆blocksize_CurGET_SIZE(HDRP(ptr));if(asizeblocksize_Cur){return ptr; }else if(asizeblocksize_Cur){ //当前块的大小要求分配的空间大小if(blocksize_Cur-asizeMINBLOCK)place(ptr,asize);return ptr;}else{ //当前块的大小要求分配的空间大new_ptrfind_fit(asize);if(new_ptrNULL){ //如果当前链表找不到合适的块则申请额外的空间extendsizeMAX(CHUNKSIZE,asize);if((new_ptrextend_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都会报下面的错误。这也是浪费最多时间的一部分。
