当前位置： 代码迷 >> 综合 >> CSAPP: MallocLab杀我
  详细解决方案

CSAPP: MallocLab杀我

热度：8   发布时间：2023-12-06 12:12:23.0

学ICS以来花费最长时间的lab（手动狗头
大概是我第九章学的不好…

感谢各位大佬！！
https://www.cnblogs.com/liqiuhao/p/8252373.html
https://www.bilibili.com/read/cv2972577/
mm_check大佬：
https://www.jianshu.com/p/48d5d0554b3b
再次感谢！！！

这个Lab需要自己实现一个内存分配器
主要实现mm_init（初始化堆）、mm_malloc（分配内存）、mm_free（释放内存）、mm_realloc（再分配）
书上花大篇幅讲的是隐式链表（在头部记录块大小，查找时需依次遍历查找，所以速度较慢），看了大佬们的实验发现隐式链表得分不高，所以直接选择了显式空闲链表（把空闲块单独取出组织成链表，查找时不需要遍历已分配块，不允许定义数组所以通过&int实现），组织链表的方式选择了分离链表（共16个链表，每个储存[2k,2k+1)大小的空闲块，并且按递增顺序排列），查找时选择分离适配（即首次适配，因为块是由小到大组织的，相当于最佳适配），最后性能得分97分
为了更好的解决碎片问题，需要自己写几个static函数，包括extend_heap（扩展堆，相当于sbrk）、coalesce（根据头部脚部合并前后空闲块，书上有明确的解释）、place（在 mm_malloc时分配剩下的空间再插回list）、insert（插入空闲块）、delete（删除空闲块）
最后还要实现mm_check检查堆和块的情况
在实现上，参考了书上给出的#define方式，很好用，买它

预编译部分：

#define ALIGNMENT 8
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1<<12) 
#define MAX(x, y) ((x)>(y) ? (x) : (y))
#define LISTMAX 16
//#define DEBUG 1/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)#define SET_PTR(p, q) (*(unsigned int *)(p)=(unsigned int)(q))
#define GET(p) (*(unsigned int *)(p))//get value
#define PUT(p, val) (*(unsigned int *)(p)=(val))
#define PACK(size, alloc) ((size) | (alloc))
#define HDRP(bp) ((char *)(bp) - WSIZE)//get hdr
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp))-DSIZE)
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define SUCC_BLKP(bp) ((char *)(bp) + GET_SIZE((char *)(bp) - WSIZE))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp) - DSIZE))
#define PRED_PTR(ptr) ((char *)(ptr))//prev free block
#define SUCC_PTR(ptr) ((char *)(ptr + WSIZE))
#define PRED(ptr) (*(char **)(ptr))
#define SUCC(ptr) (*(char **)(ptr+WSIZE))

全局变量：

static char *heap_listp;
/* segregate free list */
static int segregate_list0;
static int segregate_list1;
static int segregate_list2;
static int segregate_list3;
static int segregate_list4;
static int segregate_list5;
static int segregate_list6;
static int segregate_list7;
static int segregate_list8;
static int segregate_list9;
static int segregate_list10;
static int segregate_list11;
static int segregate_list12;
static int segregate_list13;
static int segregate_list14;
static int segregate_list15;

来康一下每个部分的实现：

mm_init：
int mm_init(void)
{
    int listnum;for(listnum=0; listnum<LISTMAX; listnum++){
    SET_PTR(segregate_list(listnum), NULL);}//initiate listsif((heap_listp=mem_sbrk(4*WSIZE))==(void *)-1)return -1;PUT(heap_listp, 0);PUT(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));//epilogue headerheap_listp+=(2*WSIZE);if(extend_heap(CHUNKSIZE/WSIZE) == NULL)return -1;return 0;
}
mm_malloc：
void *mm_malloc(size_t size)
{
    int listnum=0;void *p=NULL;if(size==0) return NULL;if(size<=DSIZE) size=2*DSIZE;//min blockelse size=ALIGN(size+DSIZE);//alignmentsize_t tmp=size;while(listnum<LISTMAX)//find proper list{
    //这里要注意分离链表的取值if((tmp<=1) && ((void *)(*(unsigned int *)(segregate_list(listnum)))!=NULL)){
    p=(void *)*(unsigned int *)(segregate_list(listnum));while((p!=NULL) && (size>GET_SIZE(HDRP(p))))p=SUCC(p);//find proper free blockif(p!=NULL)break;//success}tmp>>=1;listnum++;}if(p==NULL)//can't find proper block in the list, extend the heap{
    	if((p=extend_heap(MAX(size, CHUNKSIZE)))==NULL)return NULL;}p=place(p, size);//deal with the remaining size#ifdef DEBUGprintf("malloc size:%u\n",size);
#endifreturn p;}
mm_free：
void mm_free(void *ptr)
{
    size_t size=GET_SIZE(HDRP(ptr));PUT(HDRP(ptr), PACK(size, 0));PUT(FTRP(ptr), PACK(size, 0));insert(ptr, size);//insert freed block into the listscoalesce(ptr);//coalesce prev & succ free blocks#ifdef DEBUGprintf("free size:%d\n",size);
#endif
}
mm_realloc：
void *mm_realloc(void *ptr, size_t size)
{
    void *new_ptr = ptr;int avail;if(size==0) {
    mm_free(ptr);return NULL;}if(size<=DSIZE) size=2*DSIZE;else size=ALIGN(size+DSIZE);//alignment//if new_size<cur_size, return old ptrif(GET_SIZE(HDRP(ptr))>=size)return ptr;else if(!GET_SIZE(HDRP(SUCC_BLKP(ptr))) || (!GET_ALLOC(HDRP(SUCC_BLKP(ptr))) && !GET_SIZE(SUCC_BLKP(SUCC_BLKP(HDRP(ptr)))))) 
//check if next block is free{
    avail=GET_SIZE(HDRP(ptr))+GET_SIZE(HDRP(SUCC_BLKP(ptr)));if(avail<size){
    //have to extend heapif(extend_heap(MAX((size-avail), CHUNKSIZE))==NULL)return NULL;avail+=MAX((size-avail), CHUNKSIZE);}delete(SUCC_BLKP(ptr));//use the next free blockPUT(HDRP(ptr), PACK(avail, 1));PUT(FTRP(ptr), PACK(avail, 1));//edit}else if(!GET_ALLOC(SUCC_BLKP(HDRP(ptr))) && (GET_SIZE(HDRP(ptr))+GET_SIZE(HDRP(SUCC_BLKP(ptr)))>=size)){
    delete(SUCC_BLKP(ptr));avail=GET_SIZE(HDRP(ptr))+GET_SIZE(HDRP(SUCC_BLKP(ptr)));PUT(HDRP(ptr), PACK(avail, 1));PUT(FTRP(ptr), PACK(avail, 1));}else{
    //next block is allocated, mallocnew_ptr=mm_malloc(size);memcpy(new_ptr, ptr, GET_SIZE(HDRP(ptr)));mm_free(ptr);}return new_ptr;
}

之后是自己实现的函数：

segregate_list：
static void *segregate_list(int index)
{
    switch(index){
    case 0:return &segregate_list0;case 1:return &segregate_list1;case 2:return &segregate_list2;case 3:return &segregate_list3;case 4:return &segregate_list4;case 5:return &segregate_list5;case 6:return &segregate_list6;case 7:return &segregate_list7;case 8:return &segregate_list8;case 9:return &segregate_list9;case 10:return &segregate_list10;case 11:return &segregate_list11;case 12:return &segregate_list12;case 13:return &segregate_list13;case 14:return &segregate_list14;case 15:return &segregate_list15;}return NULL;
}//大佬们用了define，而我就这么实现啦嘻嘻
extend_heap：
static void *extend_heap(size_t size)
{
    		void *ptr;size=ALIGN(size);//alignmentif((ptr=mem_sbrk(size))==(void *)-1)return NULL;PUT(HDRP(ptr), PACK(size, 0));PUT(FTRP(ptr), PACK(size, 0));PUT(HDRP(SUCC_BLKP(ptr)), PACK(0, 1));//end block of the heapinsert(ptr, size);//insert extended size into the free listreturn coalesce(ptr);
}
insert：
static void insert(void *ptr, size_t size)
{
    int listnum=0;void *prev=NULL;void *succ=NULL;int tmp=size;while((listnum<(LISTMAX-1)) && (tmp>1)){
    tmp>>=1;listnum++;}//find the right list
#ifdef DEBUGprintf("insert size:%u into %d\n",size, listnum);
#endifsucc=(void *)*(unsigned int *)segregate_list(listnum);while((succ!=NULL) && (size>GET_SIZE(HDRP(succ)))){
    prev=succ;succ=SUCC(succ);//find the right place}if(prev!=NULL){
    if(succ!=NULL)//prev->insert->succ{
    SET_PTR(PRED_PTR(ptr), prev);SET_PTR(SUCC_PTR(prev), ptr);SET_PTR(SUCC_PTR(ptr), succ);SET_PTR(PRED_PTR(succ), ptr);}else //prev->insert->NULL{
    SET_PTR(PRED_PTR(ptr), prev);SET_PTR(SUCC_PTR(prev), ptr);SET_PTR(SUCC_PTR(ptr), NULL);}}else{
    if(succ!=NULL)//segregate_list(listnum)==insert->succ{
    SET_PTR(PRED_PTR(ptr), NULL);SET_PTR(SUCC_PTR(ptr), succ);SET_PTR(PRED_PTR(succ), ptr);SET_PTR(segregate_list(listnum), ptr);}else //segregate_list(listnum)==insert{
    SET_PTR(PRED_PTR(ptr), NULL);SET_PTR(SUCC_PTR(ptr), NULL);SET_PTR(segregate_list(listnum), ptr);}}}
delete：
static void delete(void *ptr)
{
    int listnum=0;size_t size=GET_SIZE(HDRP(ptr));while((listnum<LISTMAX-1) && (size>1)){
    size>>=1;listnum++;}//find the right listif(PRED(ptr)!=NULL){
    		if(SUCC(ptr)!=NULL)//prev->block->succ{
    SET_PTR(SUCC_PTR(PRED(ptr)), SUCC(ptr));SET_PTR(PRED_PTR(SUCC(ptr)), PRED(ptr));}else//segregate_list(listnum)==prev->block{
    SET_PTR(SUCC_PTR(PRED(ptr)), NULL);}}else{
    		if(SUCC(ptr)!=NULL)//segregate_list(listnum)==block->succ{
    SET_PTR(PRED_PTR(SUCC(ptr)), NULL);SET_PTR(segregate_list(listnum), SUCC(ptr));}else//segregate_list(listnum)==block->NULL{
    SET_PTR(segregate_list(listnum), NULL);}}
}
coalesce：
static void *coalesce(void *ptr)
{
    	int prev_alloc=GET_ALLOC(FTRP(PREV_BLKP(ptr)));int succ_alloc=GET_ALLOC(HDRP(SUCC_BLKP(ptr)));size_t size=GET_SIZE(HDRP(ptr));
#ifdef DEBUGprintf("prev_alloc:%d, succ_alloc:%d\n",prev_alloc,succ_alloc);
#endifif(prev_alloc && succ_alloc) {
    return ptr;}//no need to coalesceelse if(prev_alloc && !succ_alloc){
    //coalesce succ block
#ifdef DEBUGprintf("succ:%u\n",GET_SIZE(HDRP(SUCC_BLKP(ptr))));
#endifdelete(ptr);delete(SUCC_BLKP(ptr));size+=GET_SIZE(HDRP(SUCC_BLKP(ptr)));//just modify current blockPUT(HDRP(ptr), PACK(size, 0));PUT(FTRP(ptr), PACK(size, 0));}else if(!prev_alloc && succ_alloc){
    //coalesce prev block
#ifdef DEBUGprintf("prev:%u\n",GET_SIZE(HDRP(PREV_BLKP(ptr))));
#endifdelete(ptr);delete(PREV_BLKP(ptr));size+=GET_SIZE(HDRP(PREV_BLKP(ptr)));PUT(FTRP(ptr), PACK(size, 0));PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));//modify prev blockptr=PREV_BLKP(ptr);}else{
    //coalesce prev & succ block
#ifdef DEBUGprintf("prev:%u, succ:%u\n",GET_SIZE(HDRP(PREV_BLKP(ptr))),GET_SIZE(FTRP(SUCC_BLKP(ptr))));
#endifdelete(ptr);delete(PREV_BLKP(ptr));delete(SUCC_BLKP(ptr));size+=GET_SIZE(HDRP(PREV_BLKP(ptr)))+GET_SIZE(FTRP(SUCC_BLKP(ptr)));PUT(HDRP(PREV_BLKP(ptr)), PACK(size, 0));PUT(FTRP(SUCC_BLKP(ptr)), PACK(size, 0));ptr=PREV_BLKP(ptr);}insert(ptr,size);//insert into segregate_listsreturn ptr;
}
place：
static void *place(void *ptr, size_t size)
{
    size_t ptr_size=GET_SIZE(HDRP(ptr));size_t remainder=ptr_size-size;//remaining sizedelete(ptr);if(remainder<DSIZE*2)//smaller than min, ingore{
    PUT(HDRP(ptr), PACK(ptr_size, 1));PUT(FTRP(ptr), PACK(ptr_size, 1));}else if(size>=96)//consider different sizes to avoid external fragments{
    	PUT(HDRP(ptr), PACK(remainder, 0));PUT(FTRP(ptr), PACK(remainder, 0));PUT(HDRP(SUCC_BLKP(ptr)), PACK(size, 1));PUT(FTRP(SUCC_BLKP(ptr)), PACK(size, 1));insert(ptr, remainder);return SUCC_BLKP(ptr);}else{
    PUT(HDRP(ptr), PACK(size, 1));PUT(FTRP(ptr), PACK(size, 1));PUT(HDRP(SUCC_BLKP(ptr)), PACK(remainder, 0));PUT(FTRP(SUCC_BLKP(ptr)), PACK(remainder, 0));insert(SUCC_BLKP(ptr), remainder);}return ptr;}

然后是检查堆的函数

check_block：
static int check_block(void *ptr)
{
    if((size_t)ptr % 8){
    printf("Error: %p is not aligned\n", ptr);return 0;}//check alignmentif(GET(HDRP(ptr)) != GET(FTRP(ptr))){
    printf("Error: header doesn't match footer\n");return 0;}//check header and footerreturn 1;
}/* check segregate lists */
static int check_list(void *ptr, size_t size)
{
    void *prev=NULL;long hsize, halloc;for(;ptr!=NULL; ptr=SUCC(ptr)){
    	if(PRED(ptr)!=prev) {
    printf("Error: prev doesn't match\n");return 0;}//check prev if(prev!=NULL && SUCC(prev)!=ptr) {
    printf("Error: succ doesn't match\n");return 0;}//check succhsize=GET_SIZE(HDRP(ptr));halloc=GET_ALLOC(HDRP(ptr));if(halloc) {
    printf("Error: block not free\n");return 0;}//check unfreed blockif(prev!=NULL && (GET_SIZE(HDRP(prev))>hsize)) {
    printf("Error: list order\n");return 0;}//check increasing orderif((hsize<size) || (size!=(1<<15) && (hsize>(size<<1)-1))){
    printf("Error: list size\n");return 0;}//check list sizeprev=ptr;}return 1;
}/* check the heap */
static int mm_check(void)
{
    char *bp=heap_listp;if((GET_SIZE(HDRP(heap_listp))!=DSIZE || !GET_ALLOC(HDRP(heap_listp)))){
    printf("Error: prologue header\n");return 0;}check_block(heap_listp);int prev_free=0;for(bp=heap_listp; GET_SIZE(HDRP(bp))>0; bp=SUCC_BLKP(bp)){
    	int cur_free=check_block(bp);if(prev_free && cur_free){
    printf("Error: uncoalesced free blocks\n");return 0;}}int i=0, size=1;for(; i<LISTMAX; i++){
    check_list(segregate_list(i), size);size<<=1;}if((GET_SIZE(HDRP(bp))!=0 || !(GET_ALLOC(HDRP(bp))))){
    printf("Error: epilogue header\n");return 0;}return 1;
}

完结撒花～（真的是死刚了好久
存在几个问题：
1.框架搭好之后不停segmentation fault，查出来基本都是打字错误
甚至有#define CHUNKSIZE (1<12) 这种错（微笑
core dumped的问题可以通过gdb查看错误点：
在这里插入图片描述
谢谢大佬：
https://blog.csdn.net/fcryuuhou/article/details/8507775

2.第一次跑的结果很奇怪，后面复杂的检测利用率很高，反而是最初的利用率极低
在这里插入图片描述
最后发现还是写错了，我也是服了自己…
最后一次的情况也是类似，又又是我写错了…
在这里插入图片描述
3.小菜鸡是跟着大佬们盲写的！！能上岸无比幸福～
ICS期中考冲冲冲！！

完结撒花～
在这里插入图片描述

  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.