CS:APP Malloc Lab
实验需求
在这个实验中，你将为C程序编写一个动态存储分配器，也就是你自己版本的malloc、free和realloc例程。
您的动态存储分配器将由以下四个函数组成，它们在mm.h中声明，在mm.c中定义。
int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);
修改这些函数(并可能定义其他私有静态函数)，使它们遵循以下语义:
- mm_init：评估实现的跟踪驱动程序在启动时会调用mm_init来执行任何必要的初始化，例如分配初始堆区域。如果在执行初始化时出现问题，返回值应该是-1，否则为0。
- mm_malloc：返回一个指向至少size字节的已分配块负载部分的指针。整个分配的块应该位于堆区域内，并且不应该与任何其他分配的块重叠，始终返回8字节对齐的指针。
- mm_free：释放ptr所指向的块，它什么也不返回。
- mm_realloc：返回一个指针，该指针指向至少size字节的已分配区域，并具有以下约束
- 如果ptr为NULL，则调用相当于mm_malloc(size);
- 如果size等于0，则调用等于mm_free(ptr);
- 如果ptr不是NULL，则将ptr所指向的内存块(旧块)的大小更改为size字节，保证前size字节内容不变，并返回新块的地址。
- 请注意：新块的地址可能与旧块相同，也可能不同，这取决于您的实现、旧块中的内部碎片数量和realloc请求的大小。
memlib.c包为动态内存分配器模拟内存系统。您可以调用memlib.c中的以下函数：
void *mem_sbrk(int incr); //将堆扩展为incr字节，其中incr是一个非零正整数，并返回指向新分配堆区域的第一个字节的泛型指针。其语义与Unix的sbrk函数相同，只是mem sbrk只接受一个非零的正整数参数。
void *mem_heap_lo(void); //返回指向堆中第一个字节的泛型指针。
void *mem_heap_hi(void); //返回指向堆中最后一个字节的泛型指针。
size mem_heapsize(void); //以字节为单位返回堆的当前大小。
size mem_pagesize(void); //以字节为单位返回系统的页面大小(在Linux系统上为4K)。
The solution
我们选择使用分离适配(链表数组) + 显式空闲链表(双向链表)的方式来组织分配器。
空闲块形式如下图所示：
根据空闲块的形式我们可定义一些操作空闲链表的基本常数和宏：
注：下述bp代表的是指向suss部分的指针
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE 1<<4 //扩展堆时的默认大小
#define ALIGN(size) (((size) + 7) & ~0x7)//8字节对齐
#define MAX(x,y) ((x) > (y)? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p) (*(unsigned int*)(p))//解引用
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define PUT(p, val) (*(unsigned int*)(p) = (unsigned int)(val))
#define HDRP(bp) ((char*)(bp) - DSIZE)//获取头部
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - (WSIZE * 3))//获取脚部
#define NEXT_PTR(bp) ((char*)(bp))//获取指向下一结点指针
#define PREV_PTR(bp) ((char*)(bp) - WSIZE)//获取指向上一结点指针
#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)))//获取下一块的bp地址
#define PREV_BLKP(bp) ((char*)(bp) - GET_SIZE((char*)(bp) - (WSIZE * 3)))//获取上一块的bp地址
对于大小类的划分，我们可以根据2的幂来划分。结合空闲块形式和8字节对齐的要求，我们可以得出最小空闲块大小为：8(头脚部)+8(前后指针) = 16 字节，故可得出具体的大小类划分如下：
mm_init
我们将上述首元结点数组初始化于堆的开头部分，在此之后分配序言块和结尾块令后续的空闲块合并操作不需特判，接着以堆的默认扩展大小分配一个初始空闲块。
这里需要注意的是序言块+结尾块并不能满足8字节对齐，故我们还需在前插入一个填充块。
具体代码如下所示：
static char *heap_bg;//指向堆的开头
int mm_init(void)
{
int i;
if((heap_bg = mem_sbrk(14 * WSIZE)) == (void*) -1)
return -1;
for(i = 0; i < 10; i++)//填充首元结点数组，链表以-1结尾
PUT(heap_bg + (i * WSIZE), -1);
PUT(heap_bg + (10 * WSIZE),0);//填充块
PUT(heap_bg + (11 * WSIZE), PACK(DSIZE, 1));//序言块
PUT(heap_bg + (12 * WSIZE), PACK(DSIZE, 1));
PUT(heap_bg + (13 * WSIZE), PACK(0, 1));//边界块
if(extend_heap(CHUNKSIZE) == NULL)//分配初始空闲块
return -1;
return 0;
}
extend_heap
该函数扩展堆以获取可用空闲块。bp = bp + WSIZE的作用是将原结尾块作为新块头部并将bp指针移动到suss部分开头，令后续宏定义生效。
具体代码如下所示：
static void *extend_heap(size_t words){
char *bp;
size_t size = ALIGN(words);//对齐
if((long)(bp = mem_sbrk(size)) == -1)//扩展堆
return NULL;
bp = bp + WSIZE;
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));//结尾块
return coalesce(bp);//合并空闲块
}
链表操作函数
后续函数会涉及空闲块的存取操作，故先给出链表操作函数定义：
void *get_ptr(size_t size){//获取头指针(指向首元节点)
size_t idx = 0;
if(size >= 8192)// >=8192归为一类
return (void*)(heap_bg + 9 * WSIZE);
while(size){
size /= 2;
idx++;
}
return (void*)(heap_bg + (idx-5) * WSIZE);
}
static void add_block(void *bp, size_t size){//将空闲块加入链表
void *ptr = get_ptr(size);
if(GET(ptr) != -1)
PUT(PREV_PTR(GET(ptr)), bp);
PUT(NEXT_PTR(bp), GET(ptr));
PUT(ptr, bp);
PUT(PREV_PTR(bp), ptr);//指向首元结点
}
static void erase_block(void *bp){//将空闲块从链表移出
void *next_bp = NEXT_PTR(bp);
void *prev_bp = PREV_PTR(bp);
if(GET(prev_bp) <= (unsigned)(heap_bg + 9 * WSIZE))//头结点无前置结点
PUT(GET(prev_bp), GET(next_bp));
else
PUT(NEXT_PTR(GET(prev_bp)), GET(next_bp));
if(GET(next_bp) != -1)
PUT(PREV_PTR(GET(next_bp)), GET(prev_bp));
}
coalesce
该函数的作用是检查空闲块在堆上的前后块是否空闲，若空闲则将其移出链表，与中间空闲块拼接后再将放回链表。
static void *coalesce(void *bp){
size_t size = GET_SIZE(HDRP(bp));//获取原块大小
size_t prev_size = GET_SIZE(HDRP(PREV_BLKP(bp)));//前块大小
size_t prev_alloc = GET_ALLOC(HDRP(PREV_BLKP(bp)));//前块空闲标记位
size_t next_size = GET_SIZE(HDRP(NEXT_BLKP(bp)));//后块大小
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));//后块空闲标记位
if(!prev_alloc && next_alloc){//前一块未使用
erase_block(PREV_BLKP(bp));//将前空闲块从链表中移出
size += prev_size;
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
bp = PREV_BLKP(bp);
}
else if(prev_alloc && !next_alloc){//后一块未使用
erase_block(NEXT_BLKP(bp));//将后空闲块从链表中移出
size += next_size;
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
PUT(HDRP(bp), PACK(size, 0));
}
else if(!prev_alloc && !next_alloc){//前后块都未使用
erase_block(PREV_BLKP(bp));//将前后空闲块从链表中移出
erase_block(NEXT_BLKP(bp));
size += next_size + prev_size;
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
add_block(bp, size);//将合并后空闲块加入链表
return bp;
}
mm_malloc
该函数为用户提供所需堆内存，该函数的主体流程就是先从空闲链表中以首次匹配的方式寻找能够满足需求的空闲块，若找得到则将其取出，若不能则需要扩展堆以获取空闲块。
最后检查一下空闲块填充了负载后内部碎片会不会过大，若内部碎片过大则需要将其分割成空闲块放回空闲链表。
需要注意的是空闲块与分配块的区别，分配块的有效荷载部分是从原空闲块的pred部分开始的，而bp指针指向的是空闲块suss部分，故要向前偏移4字节，令返回的指针指向分配块有效荷载部分。
void *mm_malloc(size_t size)
{
size_t asize;
size_t extendsize;
char *bp;
if(!size)
return NULL;
asize = ALIGN(size + DSIZE);//有效负载+头脚部
if((bp = find_fit(asize)) != NULL){//有可用空闲块
place(bp, asize);//尝试避免内部碎片
bp = bp - WSIZE;//将其回移动4字节
return bp;
}
extendsize = MAX(asize, CHUNKSIZE);
if((bp = extend_heap(extendsize)) == NULL)//扩展堆以获取空闲块
return NULL;
place(bp, asize);//尝试避免内部碎片
bp = bp - WSIZE;//将其回移动4字节
return bp;
}
find_fit
该函数实现在链表中以首次适配的方式查找可用空闲块，若找不到则返回NULL
static void *find_fit(size_t asize){//首次适配
char *ptr = get_ptr(asize);//获取头指针（指向首元结点）
char *max_addr = heap_bg + 10 * WSIZE;
char *bp;
size_t mark = 1;
while(mark){
bp = (char*)GET(ptr);//获取指向头结点的指针
while((int)bp != -1){//遍历整个链表
if(GET_SIZE(HDRP(bp)) >= asize){//找到符合需求的空闲块
mark = 0;
break;
}
bp = (char*)GET(NEXT_PTR(bp));
}
ptr += WSIZE;//换下一个头指针
if(ptr == max_addr)//所有链表都找完了
break;
}
if(mark) return NULL;
else return bp;
}
place
该函数将检查从空闲链表中取出的空闲块在装载完有效荷载后内部碎片是否大于一定大小，若超过设定大小则将其分割出来变为空闲块，并将其放回空闲链表。
这里需要注意的是设定值不能设定的太小不然的话容易造成外部碎片过多。
static void place(void *bp, size_t asize){
erase_block(bp);//将空闲块从空闲链表中拿出
size_t size = GET_SIZE(HDRP(bp)) - asize;
if(size >= DSIZE*4){//需要分割
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
PUT(HDRP(NEXT_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
add_block(NEXT_BLKP(bp), size);//将分割剩余块放入空闲列表
}
else{
PUT(HDRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
PUT(FTRP(bp), PACK(GET_SIZE(HDRP(bp)), 1));
}
}
mm_free
该函数用于回收内存，需要注意的是用户传入的ptr指向的位置是分配块有效荷载的部分，需要将其后移4字节才能获得操作空闲块的bp，与mm_malloc的移动是对应的。
void mm_free(void *ptr)
{
char *bp = ptr;
bp = bp + WSIZE;//将其后移4字节
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);//合并空闲块
}
mm_realloc
该函数将调整有效荷载的大小。
当传入的ptr非NULL时，我们可分以下几种情况讨论：
- 原分配块的有效荷载大小大于用户需要的大小，则判断多余的部分造成的内部碎片大小是否超出设定值，若超出则将其分割出来作为空闲块并放入空闲链表。在本情况下最后返回原指针即可。
- 原分配块的有效荷载大小小于于用户需要的大小小，继续判断：如果在堆上的下一块是空闲块且本块和下一块的大小加起来够用，则把下一块从空闲链表中取出，把这两个块合并后给用户；否则，就调用mm_malloc申请一个新的块，把原块中的内容memcpy，把原块释放掉，再把新块给用户。
void *mm_realloc(void *ptr, size_t size)
{
if(ptr == NULL)
return mm_malloc(size);
else if(!size){
mm_free(ptr);
return NULL;
}
char *bp = ptr;
bp = bp + WSIZE;
size_t bsize = GET_SIZE(HDRP(bp));
size_t asize = ALIGN(size + DSIZE);
if(bsize >= asize){//有效荷载大小大于用户需求
size_t dvalue = bsize - asize;
if(dvalue >= DSIZE*4){//多出部分可单独成块
PUT(HDRP(bp), PACK(asize, 1));//调整原块大小
PUT(FTRP(bp), PACK(asize, 1));
PUT(HDRP(NEXT_BLKP(bp)), PACK(dvalue, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(dvalue, 0));
coalesce(NEXT_BLKP(bp));//将分割剩余块放入空闲列表
}
return ptr;
}
else{//有效荷载大小小于用户需求
if(GET_ALLOC(HDRP(NEXT_BLKP(bp))) == 0 && GET_SIZE(HDRP(NEXT_BLKP(bp))) + bsize >= asize){
erase_block(NEXT_BLKP(bp));
size_t avalue = GET_SIZE(HDRP(NEXT_BLKP(bp))) + bsize;
PUT(HDRP(bp), PACK(avalue, 1));
PUT(FTRP(bp), PACK(avalue, 1));
return ptr;
}
else{
void *newptr = mm_malloc(size);
memcpy(newptr, ptr, size);
mm_free(ptr);
return newptr;
}
}
}
测试结果
测试集下载
对于该测试集，本人实现的malloc吞吐量是标准库中malloc的两倍
