CSAPP-malloc lab

实现思路

所用策略：Segregated lists + best fits + explicit free list

堆的结构：
地址从上到下是从低到高

分离适配的原理：

allocator 维护一个空闲链表的数组，每个空闲链表是和一个大小类相关联的，被组织成某种类型的显式或者隐式链表，每个链表包含潜在的大小不同的块。

为了分配，要先确定请求的大小的类，并且对适当的空闲链表做首次适配，如果找到，就分割，并把剩余部分查到空闲链表。如果找不到，就搜索下一个更大的类，如果还是没有，就向操作系统请求额外的堆内存，然后从这个堆内存中分配出一个块，并把剩余部分放在适当的大小类中。

/* 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 WSIZE 4 //word and header/footer size
#define DSIZE 8 //double word size (bytes)

#define INITCHUNKSIZE (1<<6) //the size of extended heap 
#define CHUNKSIZE (1<<12) //extend heap 

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

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

//read and write a word at addr p
#define GET(p) (*(unsigned int*)(p))
#define PUT(p,val) (*(unsigned int*)(p) = (val))

#define SET_PTR(p,ptr) (*(unsigned int*)(p) = (unsigned int)(ptr))

#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)
// (char*bp)+size -wsize= next's block's bp 's position,-DSIZE,that means 
//  previous block's foot address
#define FTRP(bp)  ((char*)(bp)+GET_SIZE(HDRP(bp))-DSIZE)

#define NEXT_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))
#define SUCC_PTR(ptr) ((char*)(ptr)+WSIZE)

#define PRED(ptr) (*(char **)(ptr))
#define SUCC(ptr) (*(char **)(SUCC_PTR(ptr)))

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define LIST_SIZE 16

全局函数

static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *place(void *bp,size_t asize);
static void insert(void *bp,size_t size);
static void delete(void *bp);

初始化列表

/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    void *heap;
    if((heap=mem_sbrk(4*WSIZE))==(void*)-1)
        return -1;
    
    int idx;
	
    //initialize the list
    for(idx=0;idx<LIST_SIZE;idx++){
        list[idx] = NULL;
    }
   
    //alignment padding
    //按照上图堆的结构来初始化
    PUT(heap,0);
    PUT(heap+(1*WSIZE),PACK(DSIZE,1));  //prologue header
    PUT(heap+(2*WSIZE),PACK(DSIZE,1)); //prologue footer
    PUT(heap+(3*WSIZE),PACK(0,1)); //Epilogue header

    if(extend_heap(INITCHUNKSIZE)==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)
{
    //ignore spurious requeses
    if(size==0)
        return NULL;
    
    if(size<=DSIZE)
        size = 2*DSIZE;
    else
        size = ALIGN(size+DSIZE);

    int idx = 0;
    size_t ssize = size;
    void *ptr = NULL;

    while(idx<LIST_SIZE){
		//链表类的大小分别是 1 1 2 4 8 16 32...
        // 分别存储 {0},{1},{2,3},{4,5,6,7}..
        // 通过循环 ssize>>=1 与idx,找到该分配的
        //字节大小所在的链表
        //然后再内嵌一个循环，在这个链表中寻找大小适			//合的pointer
        if((ssize<=1)&&(list[idx]!=NULL)){
            ptr = list[idx];
            while(ptr&&((size>GET_SIZE(HDRP(ptr))))){
                ptr = PRED(ptr);
            }
            //如果找到了就break
            if(ptr!=NULL)
                break;
        }
        ssize>>=1;
        idx++;
    }

    //如果找不到，向系统申请额外的堆内存
    if(ptr==NULL){
        int extendsize = MAX(size,CHUNKSIZE);
        if((ptr=extend_heap(extendsize))==NULL)
            return NULL;
    }
    
    //在free块中allocate size大小的块
    ptr = place(ptr,size);

    return ptr;
}

void mm_free(void *ptr)
{
    size_t size = GET_SIZE(HDRP(ptr));

	//把该块头脚末位都标注为0，说明这一块是free
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));

    /* 插入分离空闲链表 */
    insert_node(ptr, size);
    /* 合并 */
    coalesce(ptr);
}