Lab5 Malloc Lab

Lab5 Malloc Lab

CSAPP Lab6 实验记录 ---- Malloc Lab（全实验流程 + 85 Scores）_malloclab实验-CSDN博客

CSAPP(CMU 15-213)：Lab6 Malloclab详解_csapp malloc lab-CSDN博客

这两篇可以

前言

这是篇废稿，因为自己写崩了，就真写不出来。然后有价值的就前面两篇推荐，后面就别看了。我就把隐式空闲单向链表照猫画虎地加了注释，后面的都没弄完。但不想做了。

发这篇就相当于留个爪。

一、前置

1.目的

编写一个动态内存申请器，即在mm.c中完成或修改四个函数。

extern int mm_init (void);
extern void *mm_malloc (size_t size);
extern void mm_free (void *ptr);
extern void *mm_realloc(void *ptr, size_t size);

使用不同方法改变利用率和吞吐率，逐步优化。

通过课程学习：实现方法有有Implicit list、Explicit list、Segregated list；然后是 fit algorithm，有Best fit、first fit、next fit

相关命令,基本前两条就够了

unix> make			// 构建驱动程序
unix> ./mdriver -V -f short1-bal.rep	// 在一个小型测试跟踪文件上运行驱动程序
unix> ./mdriver -h  // 获取驱动程序标志列表

查资料发现是trace不完整，然后网上博客有讲下载，就前面觉得可以的那一篇就行。

valid: 表示内存分配器实现是否通过了该测试案例。

util: 表示内存利用率，即分配的内存使用率。

ops: 表示在测试案例中执行的内存操作次数。

secs: 表示执行测试案例所花费的时间，单位是秒。

Kops: 表示每秒执行的内存操作数（千次操作数，K为千的意思）。

分数有util和thru（吞吐量）两个确定

二、编写

原先的方法

/*
 * mm-naive.c - 最快但内存利用效率最低的malloc包。
 * 
 * 在这种简单的实现中，通过简单地增加brk指针来分配块。
 * 每个块只是纯粹的数据负载。没有头部或尾部信息。
 * 块永远不会合并或重用。realloc直接使用mm_malloc和mm_free实现。
 */

（1）隐式空闲单向链表+first fit

思路：①先考虑单个块结构，为了实现方便，空闲块和已分配的块都有头和脚标记，考虑这个结构，发现其实不用额外定义，在malloc时额外申请两个字就行②然后是整体的链表，根据课上的图，肯定专门要有一个root和一尾巴。然后就是初始化对齐块③然后是实现malloc、free、relloc

①宏定义，简化操作

/* 已有宏，分别是对齐大小、对申请大小进行对齐（比如13会被对齐到16）、SIZE_T_SIZE为size_t类型对齐后大小（比如int实际字节） */
#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))

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

/* 自定义宏 */
// 状态
#define WSIZE    4        //字、脚部或头部的大小
#define DSIZE    8        //双字大小（字节）
#define CHUNKSIZE  (1<<12)   // 扩展堆时的默认大小
#define MINBLOCK (DSIZE + 2*WSIZE)	// 最小块大小：对齐+tag

// 操作p为指针
#define PACK(size, alloc)  ((size) | (alloc))	// 分配时已分配的a为1
#define GET(p)	(*(unsigned int *)(p))		// 读取p这个地方的一个字
#define PUT(p, val)   (*(unsigned int *)(p) = (val))	// 向p这个地方写一个字
#define GET_SIZE(p)  (GET(p) & ~0x07) // 得到p的size
#define GET_ALLOC(p) (GET(p) & 0x1) // 得到p的分配bit

// 操作 bp为指向有效载荷块的指针.char*可兼容
#define HDRP(bp)     ((char*)(bp) - WSIZE)  //获得头部的地址
#define FTRP(bp)     ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)  //获得脚部的地址, 与宏定义HDRP有耦合
#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;	// 指向序言块
/* private functions */
static void *extend_heap(size_t size);     //拓展堆块
static void *find_fit(size_t size);        //寻找空闲块
static void place(char *bp, size_t size);  //分割空闲块
static void *coalesce(void *bp);           //合并空闲块

②初始化链表

plus：如图，一个块为4字节（32为），因为头＋尾，两个块为最小块，所以最开始的序言块8/0哪里都是占满了，所以直接用8/1

int mm_init(void)
{
	// 先申请一个头和一个尾,按最小算，一共4*WSIZE
	if((heap_listp=mem_sbrk(4*WSIZE))==(void*)-1)
		return -1;
	PUT(heap_listp,0);	// 为了对齐，第一个字不用
	// 第2、3个字为序言块,分别为头、有效载荷
	PUT(heap_listp+1*WSIZE,PACK(8,1));
	PUT(heap_listp+2*WSIZE,PACK(8,1));
	// 最后一个字为结尾0/1
	PUT(heap_listp+3*WSIZE,PACK(0,1));
	
	heap_listp += (2*WSIZE);	// 技巧，指向序言块中间
	
	// 看堆还能是否再申请
	if(extend_heap(CHUNKSIZE)==NULL)
		return -1;
}

③malloc操作

// 申请大小为size的块
void *mm_malloc(size_t size)
{
	size_t asize;			// 加上tag后的块大小
	size_t extendsize;
	void *bp = NULL;

	if(size==0)	return NULL;
	asize = ALIGN(size + 2*WSIZE);	// 头+尾，然后对齐
	
	// 刚好有一块大小够
	if((bp = find_fit(asize))!=NULL)
	{
		place((char *)bp,asize);
		return bp;
	}
	
	// 没有合适的大小空闲块
	extendsize = MAX(asize,CHUNKSIZE);
	if((bp = extend_heap(extendsize)) == NULL)
		return NULL;
	place(bp,asize);
	return bp;
}

④free操作

void mm_free(void *ptr)
{
	size_t size = GET_SIZE(ptr);
	PUT(HDRP(ptr),PACK(size,0));
	PUT(FTRP(ptr),PACK(size,0));
	coalesce(ptr);
}

⑤relloc操作

void *mm_realloc(void *ptr,size_t size)
{
	size_t old_size, new_size, extendsize;
	void *old_ptr, *new_ptr;
	
	// 特殊情况
	if(ptr==NULL)
		return mm_malloc(size);
	if(size == 0)
	{
		mm_free(ptr);
		return NULL;
	}
	
	old_size = GET_SIZE(HDRP(ptr));
	old_ptr = ptr;
	new_size = ALIGN(size + 2*WSIZE);
	// 比原来大or小
	if(old_size>=new_size)	// 比原来小，就分割
	{
		if(old_size-new_size>=MINBLOCK)
		{
			place(old_ptr,new_size);
		}else
		{
			return old_ptr;
		}
	}else		// 比原来大，就释放然后再寻找
	{
		// 如果找不到适配，扩展堆；找到new_ptr
		if((new_ptr = find_fit(new_size))==NULL)
		{
			extendsize = MAX(new_size,CHUNKSIZE);
			if((new_ptr = extend_heap(extendsize)) == NULL)	
			return NULL;
		}
		place(new_ptr,new_size);
		// 复制块内容
		memcpy(new_ptr,old_ptr,old_size-2*WSIZE);
		mm_free(old_ptr);
		
		return new_ptr;
	}
}

⑥辅助函数的实现

前面四个函数的实现抽象了一些很重要的步骤

// 首次适配，从头开始搜索
static void *find_fit(size_t size)
{
	void *curbp;
	for(curbp = heap_list;GET_SIZE(HDRP(curbp)) > 0;curbp = NEXT_BLKP(curbp))
	{
		if(!GET_ALLOC(HDRP(curbp))&&(GET_SIZE(HDRP(curbp)) >= size))
		return curbp;
	}
	
	return NULL;	// 未适配
}

// 分割
// 只要在asize的头和尾打上标记就行，但要注意最小块,就如果空余的比最小块还小，就直接整块算上，否则就分开标
static void place(char *bp,size_t asize)
{
	size_t total_size = GET_SIZE(HDRP(bp));
	size_t left_size = total_size - asize;
	
	if(left_size >= MINBLOCK)
	{
		PUT(HDRP(bp),PACK(asize,1));
		PUT(FTRP(bp),PACK(asize,1));
		bp = NEXT_BLKP(bp);
		PUT(HDRP(bp),PACK(left_size,0));
		PUT(FTRP(bp),PACK(left_size,0));
	}else
	{
		PUT(HDRP(bp),PACK(totoal_size,1));
		PUT(FTRP(bp),PACK(totoal_size,1));
	}
	
}

// 合并内存块
// 核心思想是后块就增加size大小，前块就前移bp，最后打上标记就行
static void *coalesce(void *bp)
{
	int pre_alloc  = GET_ALLOC(HDRP(PREV_BLKP(bp)));
	int post_alloc = GET_ALLOC(HDPR(NEXT_BLKP(bp)));
	size_t size = GET_SIZE(HDRP(bp));
	
	if(pre_alloc&&post_alloc)
	{
		return bp;
	}
	
	if(!post_alloc)
		size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
	if(!pre_alloc)
	{
		size += GET_SIZE(HDRP(PREV_BLKP(bp)));
		bp = PREV__BLKP(bp);
	}
	
	
	PUT(HDRP(bp),PACK(size,0));
	PUT(FTRP(bp),PACK(size,0));

	return bp;
}

// 将堆扩大size
static void *exetend_heap(size_t size)
{
	// asize为请求大小对齐处理,然后用mem_sbrk来扩展堆
	size_t asize;
	void *bp;
	asize = ALIGN(size);
	
	if((long)(bp = mem_sbrk(asize))== -1)
		return NULL;
	
	// 设置新分配块的头部和尾部
	PUT(HDRP(bp),PACK(asize,0));
	PUT(FTRP(bp),PACK(asize,0));
	
	// 设置新结尾块的头部
	PUT(HDRP(NEXT_BLKP(bp)),PACK(0,1));
	
	// 对新分配的块进行合并操作
	return coalesce(bp);
}

分析

（2）显式空闲链表+first fit

思路：①前面隐式空闲列表是通过大小相对位置跳转，而显示空闲列表是则在空闲头部块下面加了Next和Prev指向前面或者后面一个空闲块。已分配块还是和原来一样。所以增加空闲块内的两指针。

②然后就是整条链表，是空闲块链起来。root和尾巴，然后相关操作更新就行了。

整个思路在原来的隐式空闲链表上改一下就行了

①宏定义

#define MINBLOCK (DSIZE + 2*WSIZE + 2*WSIZE)
// 得到地址
#define GETADDR(p)  (*(unsigned int **)(p))
// 改变存的地址
#define PUTADDR(p,addr)	 (*(unsigned int **)(p) = (unsigned int *)(addr))
// 指向祖先指针的指针
#define PRED_POINT(bp)	(bp)
//指向后继指针的指针
#define SUCC_POINT(BP)  ((char*)(bp) + WSIZE)

static void* head_free;

②

static void insert_freelist(void *bp); 使用头插法向空闲链表中插入空闲块
static void remove_freelist(void *bp); 从空闲链表中移除空闲块，合并中使用（合并策略）
static void place_freelist(void *bp); 对空闲链表中的空闲块进行前部分割（分割策略）
static void *find_fit(size_t size); 针对链表进行搜索上的修改

三、总结

2.关于调试

#define VERBOSE 0
#ifdef DEBUG
#define VERBOSE 1
#endif

static void mm_printblock(int verbose, const char* func) {
    if (!verbose) return;
    char *curbp;
    printf("\n=========================== %s ===========================\n" ,func);
    for (curbp = heap_listp; GET_SIZE(HDRP(curbp)) > 0; curbp = NEXT_BLKP(curbp)) {
        printf("address = %p\n", curbp);
        printf("hsize = %d, fsize = %d\n", GET_SIZE(HDRP(curbp)), GET_SIZE(FTRP(curbp)));
        printf("halloc = %d, falloc = %d\n", GET_ALLOC(HDRP(curbp)), GET_ALLOC(FTRP(curbp)));
        printf("\n");
    }
    //epilogue blocks
    printf("address = %p\n", curbp);
    printf("hsize = %d\n", GET_SIZE(HDRP(curbp)));
    printf("halloc = %d\n", GET_ALLOC(HDRP(curbp)));
    printf("=========================== %s ===========================\n" ,func);
}

 mm_printblock(VERBOSE, __func__);
 
./mdriver -V -f short1-bal.rep > out.txt

#ifdef DEBUG的理解-CSDN博客

在工程设置里有一些设置会对该工程自动产生一系列的宏，用以控制程序的编译和运行。如果你把代码夹在#ifdef DEBUG 和对应的 #endif 中间，那么这段代码只有在调试（DEBUG）下才会被编译。也就是说，如果你在RELEASE模式下，这些代码根本就不会存在于你的最终代码里头。

这些宏代码本身是面向编译器使用的，不要用来实现你的业务逻辑代码,这类宏定义的一个典型应用就是产生/屏蔽调试信息。