Malloc_Lab实验报告¶
在颠簸的、即将跨年的2022年12月，就让我挑战一下早有耳闻的、困难的Malloc_Lab吧！
完整代码：
实验介绍¶
整体情况¶
实验要求我们完成一套动态内存分配器，模拟malloc,free,realloc.
完成实验需要我们理解内存布局，管理内存的数据结构，并在时间效率和空间效率上进行权衡取舍。
我们唯一需要修改的文件便是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 在调用其它三个函数之前，mdriver会先调用 mm_init 进行必要的初始化，比如分配初始堆区，如果初始化不成功，返回-1，否则返回0。
mm_malloc 返回已分配块的有效载荷payload的起始地址，其中，payload的大小至少为size字节，除此之外，必须保证已分配块在堆区里面，并且不会与其它已分配块重叠。
mm_free 释放被ptr指向的已分配块（调用mm_malloc、mm_realloc得到的ptr），如果已经被释放，什么都不干。
mm_realloc 返回一个已分配的块，其有效载荷payload的大小至少为size字节，并且有如下的限制:
如果ptr 为 NULL，那么等价于调用mm_alloc(size);
如果size等于0，那么的等价于调用mm_free(ptr);
否则，mm_realloc必须重新分配payload至少为size字节的块，并且保证新的块的内容和旧的块一致，值得注意的是，这个新块的地址有可能和旧块的地址相同，或者不同，取决于我们的实现方式。
具体还在官方文档介绍
此处有个小坑，就是不要下载2010版的Lab而用2001年老版本的，否则就会出现cc1 all warnings being treated as errors 编译错误(我们要采用32位编译模式而不是64位)
评分标准¶
性能评价指标在课本上有较详细的介绍。(课本P591)
根据CSAPP提供的框架代码，将有两个维度评估我们的内存分配器的性能，分别是空间利用率和速度。其中空间利用率主要取决于我们的分配过程中产生的内部碎片和外部碎片的大小，速度主要取决于我们的malloc和free等操作的时间复杂度，详细评估公式见官方文档。
Debug¶
其实这个Lab最难做的便是不断地调试，我经常出现一些找老半天的小错误/捂脸。
官方直接下载的压缩包只有两个数据包，数据量很小，难以顺利进行测试。后来学姐补充了一下，在项目的traces文件夹。
然后我们要将traces文件夹放在config.h的同级目录中，在config.h中间中添加宏定义#define TRACEDIR "./traces/"
我没修改Makefile里面的gcc编译选项(修改了反而各种报错) 把自己的mm.c导入后直接make,然后./mdriver -f short1-bal.rep发现有输出呢 【第一项util是空间利用率，第二项thru是吞吐量】好的，大概没什么问题了。
Team Name:Tommy
Member 1 :Tommy:10211900416@stu.ecnu.edu.cn
Perf index = 59 (util) + 40 (thru) = 99/100
然后执行mdriver来一波详细测试 ./mdriver -v -t ./traces
Team Name:Tommy
Member 1 :Tommy:10211900416@stu.ecnu.edu.cn
Using default tracefiles in ./traces/
Measuring performance with gettimeofday().
Results for mm malloc:
trace valid util ops secs Kops
0 yes 97% 5694 0.000279 20401
1 yes 99% 5848 0.000272 21484
2 yes 99% 6648 0.000329 20237
3 yes 99% 5380 0.000267 20142
4 yes 99% 14400 0.000327 43983
5 yes 94% 4800 0.000353 13594
6 yes 91% 4800 0.000354 13571
7 yes 95% 12000 0.000385 31153
8 yes 88% 24000 0.002673 8979
9 yes 99% 14401 0.000208 69369
10 yes 98% 14401 0.000178 81087
Total 96% 112372 0.005625 19979
Perf index = 58 (util) + 40 (thru) = 98/100
中间可能会出现各种Segmentation fault，这个就需要不断调试了呢。
实验过程¶
复习理论¶
这个过程主要是因为自己课本第九章学得比较零碎，本来是可以略过的。
我就来写一下第九章后半部分的主要内容吧。
3种适配方式
- 首次适配(fitst fit)
- 下一次适配(next fit)
- 最佳适配(best fit)
first fit: 最为直接的办法。扫描所有的块，只要当前块的大小满足要求就使用，速度较快。但容易导致空闲列表中前面的块被不断地细分，而后面的一些块却一直迟迟得不到利用。 second fit: 扫描的时候，每次从上一次扫描的下一个块开始，这样可以使得整个列表的块都可以被使用，这使得效率更高。然而，实际应用中，作用也很有限，容易产生很大的空间浪费，造成大量碎片。 best fit：这种方式最大的好处是可以充分地利用空间。找到所有满足要求的块中最小的那一个，这样可以很大程度上避免浪费。当然，这也使得时间成本较高，尤其是如果空间链表的组织方式不太恰当的话，容易导致每次都要遍历一整个列表。
后来在实验中我发现，采取首次适配，下一次适配，最佳适配的策略，依次是可以提高空间利用率的。但会降低速度，也就是提高搜索适配块的时间。
3种空闲列表的组织方式
-
隐式空闲链表(implicit free list)
-
显式空闲链表(explicit free list)
-
分离空闲链表(segregated free list)
implicit free list：这种方式最为简单，直接将所有的块(不管是否有分配)串在一起，然后遍历。这种方式可也使得块最小可以达到8 bytes。当然，这种方式效率很低，尤其是当块的数量较多的时候。
explicit free list：在每一个free 块中保存两个指针，将所有空闲的块组成一个双向链表。和隐式相比，这种方式最大的好处在于我们不需要遍历已经分配的块，速度上快了很多，当然，由于需要保存指针，所以每一个块最小为16 bytes。
segregated free list：这种方式的特点在于，根据块的不同大小，分成k组，组织成k条双向链表。分类的方式有很多，比如可以采用2的倍数的分类方式，{1},{2},{3~4},{5~8}……大小为6的块放在第四条链中，大小为3的块则放在第三条链中等等。
隐式空闲链表
使用长度将各块连接起来
显式空闲链表
使用指针将各个空闲块连接起来
分离空闲链表
在系统中维持多个空闲链表，每个空闲链表内放置某个大小返回内的空闲块
2种内存碎片
- 内部碎片(internal fragmentation)
- 外部碎片(external fragmentation)
internal fragmentation：内部碎片，即是已经被分配出去（能明确指出属于哪个进程）却不能被利用的内存空间。比如当前我需要44 bytes的内存，然后malloc的时候分配到了一个48 bytes的块，这样的话，剩下的4 bytes的内存尽管我不需要用到，但是其他程序也无法使用，这就是内部碎片。 external fragmentation：外部碎片，即还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域。这个比较难理解，这里用一张图来说明一下。
假设上面是内存的一部分。这个时候我如果想要一个大小为3 bytes的内存，我们发现尽管这部分总共有4 bytes的内存没有被我们用到，但是它们被隔开了，我们无法利用。因此，在这种情况下，内存中的这两个没有用到的部分就是外部碎片。需要注意的是，外部碎片和我们请求的大小有关。比如这个时候我要的如果是2 bytes大小的内存，我们发现中间的块是足够的，因此这个时候这个就不算外部碎片了。
2个合并策略
- 立即合并(immediate coalescing)
- 推迟合并(deferred coalescing)
分配器可以选 择立即合并（immediate coalescing), 也就是在每次一个块被释放时，就合并所有的相邻块。或者它也可以选择推迟合并（deferred coalescing), 也就是等到某个稍晚的时候再合并空闲块。例如，分配器可以推迟合并，直到某个分配请求失败，然后扫描整个堆，合并所有的空闲块。
块(block)的结构
使用header+payload|padding+footer，在header和footer分别占一个字(4字节)，由于块地址是双字对齐的，所以块大小为8的整数倍，这样如果用32位来存储块大小，低3位肯定都为0，所以在这里可以用最低位指示块是否是一个空闲块.
宏介绍¶
#define ALIGNMENT 8//首先是ALIGNMENT，也就是我们要8字节对齐，向8的倍数舍入。
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
//这是为size找到比它大又是最小的8的倍数
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WSIZE 4 //单字长度
#define DSIZE 8 /*Double word size*/
#define CHUNKSIZE (1 << 12) /*the page size in bytes is 4K*/
#define MAX(x, y) ((x) > (y) ? (x) : (y))//两个数中取最大值
#define PACK(size, alloc) ((size) | (alloc)) //将分配大小和标记位合并
#define GET(p) (*(unsigned int *)(p)) //读取和返回参数p引用的字
#define PUT(p, val) (*(unsigned int *)(p) = (val))//将val存放在p指向的字中
#define GET_SIZE(p) (GET(p) & ~0x7)// 从地址p处的头部或者脚部返回大小
#define GET_ALLOC(p) (GET(p) & 0x1)// 返回已分配位
#define HDRP(bp) ((char *)(bp)-WSIZE)//给定块指针，返回它的头部指针
//此bp是从有效载荷开始的，因此指向块的头部，得减去一个4字节
#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)))
//指向前面的块的块指针
版本一¶
首先我采用了最直接的方式,即首次适配+立即合并
空闲块的合并¶
根据相邻的两个块是否为空闲块来进行合并操作
static void* coalesce(void* bp) {
size_t prev_alloc=GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc=GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size=GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc)return bp;
else if (prev_alloc && !next_alloc) {
size+=GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
} else if (!prev_alloc && next_alloc) {
size+=GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp=PREV_BLKP(bp);
} else {
size+=GET_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));
bp=PREV_BLKP(bp);
}
return bp;
}
搜索适配空闲块¶
采取首次适配
static void* find_fit(size_t asize) {
char* bp;
for (bp=heap_listp; GET_SIZE(HDRP(bp))>0; bp=NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize) {return bp;}
}
return NULL;
}
放置空闲块¶
static void place(void* bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
if ((csize - asize) >= MINBLOCKSIZE) {
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp=NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
} else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
初始化¶
int mm_init(void) {
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void*)-1) return -1;
PUT(heap_listp, 0); // alignment padding
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // prologue header
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // prologue footer
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // epilogue header
heap_listp += (2 * WSIZE);
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1;
return 0;
}
mm_malloc()¶
void* mm_malloc(size_t size) {
size_t asize;
size_t extendsize; // amount to extend heap if no fit
char* bp;
if (size == 0) return NULL;
if (size <= DSIZE)asize = 2 * DSIZE;
else asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
if ((bp=find_fit(asize))!= NULL) {
place(bp, asize);
return bp;
}
// no fit found
extendsize=MAX(asize, CHUNKSIZE);
if ((bp=extend_heap(extendsize / WSIZE)) == NULL) return NULL;
place(bp,asize);
return bp;
}
mm_free()¶
void mm_free(void* bp) {
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
mm_realloc()¶
void* mm_realloc(void* ptr, size_t size) {
void* oldptr=ptr;
void* newptr;
size_t copySize;
newptr=mm_malloc(size);
if(newptr==NULL) return NULL;
size=GET_SIZE(HDRP(oldptr));
copySize=GET_SIZE(HDRP(newptr));
if (size < copySize) copySize=size;
memcpy(newptr, oldptr, copySize-WSIZE);
mm_free(oldptr);
return newptr;
}
所有的代码&评估¶
//版本一
//隐式空闲链表 立即合并 首次适配
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "memlib.h"
#include "mm.h"
#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12) /* Extend heap by this amount (bytes) */
#define MINBLOCKSIZE 2 * DSIZE
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) \
((size) | (alloc)) /* Pack a size and allocated bit into a word */
#define GET(p) (*(unsigned int*)(p)) /* read a word at address p */
#define PUT(p, val) \
(*(unsigned int*)(p) = (val)) /* write a word at address p */
#define GET_SIZE(p) (GET(p) & ~0x7) /* read the size field from address p */
#define GET_ALLOC(p) (GET(p) & 0x1) /* read the alloc field from address p */
/* given block ptr bp, compute address of its header */
#define HDRP(bp) ((char*)(bp)-WSIZE)
/* given block ptr bp, compute address of its footer */
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* given block ptr bp, compute address of next blocks */
#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)))
/* given block ptr bp, compute address of prev blocks */
#define PREV_BLKP(bp) ((char*)(bp)-GET_SIZE((char*)(bp)-DSIZE))
static char* heap_listp;
static void* extend_heap(size_t words);
static void* coalesce(void* bp);
static void* find_fit(size_t asize);
static void split_block(void* bp, size_t asize);
static void place(void* bp, size_t asize);
int mm_init(void);
void* mm_malloc(size_t size);
void mm_free(void* bp);
void* mm_realloc(void* ptr, size_t size);
team_t team = {
/* Team name */
"Tommy",
/* First member's full name */
"Tommy",
/* First member's email address */
"10211900416@stu.ecnu.edu.cn",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""};
/*
* extend heap by words * word(4 bytes)
*/
static void* extend_heap(size_t words) {
char* bp;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1) return NULL;
/* Initialize free block header/footer and the epilogue header */
PUT(HDRP(bp), PACK(size, 0)); // free block header
PUT(FTRP(bp), PACK(size, 0)); // free block footer
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // new epilogue header
return coalesce(bp); // coalesce if the previous block was free
}
static void* coalesce(void* bp) {
size_t prev_alloc=GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc=GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size=GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc)return bp;
else if (prev_alloc && !next_alloc) {
size+=GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
} else if (!prev_alloc && next_alloc) {
size+=GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp=PREV_BLKP(bp);
} else {
size+=GET_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));
bp=PREV_BLKP(bp);
}
return bp;
}
static void* find_fit(size_t asize) {
char* bp;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize) {
return bp;
}
}
return NULL;
}
static void place(void* bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
if ((csize - asize) >= MINBLOCKSIZE) {
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp=NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
} else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
int mm_init(void) {
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void*)-1) return -1;
PUT(heap_listp, 0); // alignment padding
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // prologue header
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // prologue footer
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // epilogue header
heap_listp += (2 * WSIZE);
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1;
return 0;
}
void* mm_malloc(size_t size) {
size_t asize;
size_t extendsize; // amount to extend heap if no fit
char* bp;
if (size == 0) return NULL;
if (size <= DSIZE)asize = 2 * DSIZE;
else asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
if ((bp=find_fit(asize))!= NULL) {
place(bp, asize);
return bp;
}
// no fit found
extendsize=MAX(asize, CHUNKSIZE);
if ((bp=extend_heap(extendsize / WSIZE)) == NULL) return NULL;
place(bp,asize);
return bp;
}
void mm_free(void* bp) {
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
void* mm_realloc(void* ptr, size_t size) {
void* oldptr=ptr;
void* newptr;
size_t copySize;
newptr=mm_malloc(size);
if(newptr==NULL) return NULL;
size=GET_SIZE(HDRP(oldptr));
copySize=GET_SIZE(HDRP(newptr));
if (size < copySize) copySize=size;
memcpy(newptr, oldptr, copySize-WSIZE);
mm_free(oldptr);
return newptr;
}
s10211900416@JupyterHub:~/malloc1$ ./mdriver -v -t ./traces
Team Name:Tommy
Member 1 :Tommy:10211900416@stu.ecnu.edu.cn
Using default tracefiles in ./traces/
Measuring performance with gettimeofday().
Results for mm malloc:
trace valid util ops secs Kops
0 yes 99% 5694 0.008195 695
1 yes 99% 5848 0.007574 772
2 yes 99% 6648 0.012809 519
3 yes 100% 5380 0.009392 573
4 yes 66% 14400 0.000099145308
5 yes 92% 4800 0.008238 583
6 yes 92% 4800 0.007516 639
7 yes 55% 12000 0.093942 128
8 yes 51% 24000 0.314682 76
9 yes 27% 14401 0.073848 195
10 yes 34% 14401 0.002561 5623
Total 74% 112372 0.538856 209
Perf index = 44 (util) + 14 (thru) = 58/100
结果挺惨的，都没及格/捂脸
可以看到主要问题是空间利用率不高，产生了较多的内部和外部碎片，我会在后面的内存分配器设计中进行进一步优化。比如说，隐式空闲链表并不是最好的空闲列表的组织方式，这个realloc显然是可以优化一下的。
版本二¶
将版本一中的隐式空闲链表改成显式的，顺带改一下其他的操作，这样能对性能带来多大的提高呢？这里为了简便，我先采用了后进先出(LIFO)的块排序策略(使用后进先出策略时，每次插入空闲块到空闲链表中时，都将空闲块插入到链表的头部。)
以下是需要修改的函数
空闲块的合并¶
static void* coalesce(void* bp) {
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
void* prev_bp = PREV_BLKP(bp);
void* next_bp = NEXT_BLKP(bp);
if (prev_alloc && next_alloc) {
} else if (prev_alloc && !next_alloc) {
remove_from_free_list(next_bp);
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
} else if (!prev_alloc && next_alloc) {
remove_from_free_list(prev_bp);
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
} else {
remove_from_free_list(next_bp);
remove_from_free_list(prev_bp);
size+=GET_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));
bp=PREV_BLKP(bp);
}
insert_to_free_list(bp);
return bp;
}
搜索适配空闲块¶
还是采用首次适配
static void* find_fit(size_t asize) {
char* bp;
for (bp = free_listp; bp; bp = GET_NEXT(bp)) {
if (GET_SIZE(HDRP(bp)) >= asize) {
return bp;
}
}
return NULL;
}
放置空闲块¶
略微修改
static void place(void* bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
remove_from_free_list(bp);
if ((csize - asize) >= MINBLOCKSIZE) {
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp=NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
SET_NEXT(bp, 0);
SET_PREV(bp, 0);
coalesce(bp);
} else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
mm_free()¶
略微修改
void mm_free(void* bp) {
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
SET_PREV(bp, 0);
SET_NEXT(bp, 0);
coalesce(bp);
}
所有的代码&评估¶
//版本二
// 显式空闲链表 使用后进先出的策略，将新释放的块放置在链表的开始处
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "memlib.h"
#include "mm.h"
/* 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)))
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12) /* Extend heap by this amount (bytes) */
#define MINBLOCKSIZE 2 * DSIZE
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) \
((size) | (alloc)) /* Pack a size and allocated bit into a word */
#define GET(p) (*(unsigned int*)(p)) /* read a word at address p */
#define PUT(p, val) \
(*(unsigned int*)(p) = (val)) /* write a word at address p */
#define GET_SIZE(p) (GET(p) & ~0x7) /* read the size field from address p */
#define GET_ALLOC(p) (GET(p) & 0x1) /* read the alloc field from address p */
/* given block ptr bp, compute address of its header */
#define HDRP(bp) ((char*)(bp)-WSIZE)
/* given block ptr bp, compute address of its footer */
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* given block ptr bp, compute address of next blocks */
#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)))
/* given block ptr bp, compute address of prev blocks */
#define PREV_BLKP(bp) ((char*)(bp)-GET_SIZE((char*)(bp)-DSIZE))
/*useful macro definition related to explicit free lists*/
/* next pointer and pre pointer both take up 32 bits */
#define GET_PREV(bp) (*(unsigned int*)(bp))
#define SET_PREV(bp, addr) (*(unsigned int*)(bp) = (addr))
#define GET_NEXT(bp) (*((unsigned int*)(bp) + 1))
#define SET_NEXT(bp, addr) (*((unsigned int*)(bp) + 1) = (addr))
static char* heap_listp;
static char* free_listp;
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);
int mm_init(void);
void* mm_malloc(size_t size);
void mm_free(void* bp);
void* mm_realloc(void* ptr, size_t size);
static void remove_from_free_list(void* bp) {
if (bp == NULL || GET_ALLOC(HDRP(bp))) {
return;
}
void* prev = GET_PREV(bp);
void* next = GET_NEXT(bp);
SET_PREV(bp, 0);
SET_NEXT(bp, 0);
if (prev == NULL && next == NULL) {
// only one block
free_listp = NULL;
} else if (prev == NULL) {
// bp is the first block pointer
SET_PREV(next, 0);
free_listp = next;
} else if (next == NULL) {
// bp is the last block pointer
SET_NEXT(prev, 0);
} else {
SET_NEXT(prev, next);
SET_PREV(next, prev);
}
}
static void insert_to_free_list(void* bp) {
if (bp == NULL) {
return;
}
if (free_listp == NULL) {
// free lists is empty
free_listp = bp;
SET_NEXT(bp, 0);
SET_PREV(bp, 0);
return;
}
// insert to the head of free lists
SET_PREV(bp, 0);
SET_NEXT(bp, free_listp);
SET_PREV(free_listp, bp);
free_listp = bp;
}
team_t team = {
/* Team name */
"Tommy",
/* First member's full name */
"Tommy",
/* First member's email address */
"10211900416@stu.ecnu.edu.cn",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""};
/*
* extend heap by words * word(4 bytes)
*/
static void* extend_heap(size_t words) {
char* bp;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1) return NULL;
/* Initialize free block header/footer and the epilogue header */
PUT(HDRP(bp), PACK(size, 0)); // free block header
PUT(FTRP(bp), PACK(size, 0)); // free block footer
SET_PREV(bp, 0);
SET_NEXT(bp, 0);
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // new epilogue header
return coalesce(bp); // coalesce if the previous block was free
}
static void* coalesce(void* bp) {
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
void* prev_bp = PREV_BLKP(bp);
void* next_bp = NEXT_BLKP(bp);
if (prev_alloc && next_alloc) {
} else if (prev_alloc && !next_alloc) {
remove_from_free_list(next_bp);
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
} else if (!prev_alloc && next_alloc) {
remove_from_free_list(prev_bp);
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
} else {
remove_from_free_list(next_bp);
remove_from_free_list(prev_bp);
size += GET_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));
bp = PREV_BLKP(bp);
}
insert_to_free_list(bp);
return bp;
}
static void* find_fit(size_t asize) {
char* bp;
for (bp = free_listp; bp; bp = GET_NEXT(bp)) {
if (GET_SIZE(HDRP(bp)) >= asize) {
return bp;
}
}
return NULL;
}
static void place(void* bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
remove_from_free_list(bp);
if ((csize - asize) >= MINBLOCKSIZE) {
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
SET_NEXT(bp, 0);
SET_PREV(bp, 0);
coalesce(bp);
} else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
int mm_init(void) {
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void*)-1) return -1;
PUT(heap_listp, 0); // alignment padding
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // prologue header
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // prologue footer
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // epilogue header
heap_listp += (2 * WSIZE);
free_listp = NULL;
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1;
return 0;
}
void* mm_malloc(size_t size) {
size_t asize; // adjusted block size
size_t extendsize; // amount to extend heap if no fit
char* bp;
if (size == 0) return NULL;
// adjusted block size to include overhead and alignment reqs
if (size <= DSIZE)asize = 2 * DSIZE;
else asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
// no fit found
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL) return NULL;
place(bp, asize);
return bp;
}
void mm_free(void* bp) {
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
SET_PREV(bp, 0);
SET_NEXT(bp, 0);
coalesce(bp);
}
void* mm_realloc(void* ptr, size_t size) {
void* oldptr = ptr;
void* newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL) return NULL;
size = GET_SIZE(HDRP(oldptr));
copySize = GET_SIZE(HDRP(newptr));
if (size < copySize) copySize = size;
memcpy(newptr, oldptr, copySize - WSIZE);
mm_free(oldptr);
return newptr;
}
s10211900416@JupyterHub:~/malloc1$ ./mdriver -v -t ./traces
Team Name:Tommy
Member 1 :Tommy:10211900416@stu.ecnu.edu.cn
Using default tracefiles in ./traces/
Measuring performance with gettimeofday().
Results for mm malloc:
trace valid util ops secs Kops
0 yes 89% 5694 0.000220 25929
1 yes 92% 5848 0.000151 38754
2 yes 94% 6648 0.000311 21404
3 yes 96% 5380 0.000250 21546
4 yes 66% 14400 0.000186 77419
5 yes 88% 4800 0.000482 9963
6 yes 85% 4800 0.000507 9466
7 yes 55% 12000 0.002509 4783
8 yes 51% 24000 0.002496 9614
9 yes 26% 14401 0.067671 213
10 yes 34% 14401 0.002685 5364
Total 71% 112372 0.077466 1451
Perf index = 42 (util) + 40 (thru) = 82/100
就稍微改了改，竟然就上80分了，看来将隐式空闲链表改为显式的可以较好地提高吞吐量。
版本二点五¶
本着精益求精的态度(其实是想挑战一下更高的分数)，我希望尽力来优化一下版本二。版本二我只是采用了后进先出的策略，那我稍微换一下策略，来看看结果如何。
另一种策略是按地址排序。使用按地址排序策略时，每次插入空闲块到空闲链表中时，都插入到地址大于当前空闲块的节点的前面。我们只需修改insert_to_free_list()函数，也就是插入到空闲链表的函数，根据地址大小来进行插入。
static void insert_to_free_list(void* bp) {
if (bp == NULL) {
return;
}
if (free_listp == NULL) {
// free lists is empty
free_listp = bp;
SET_NEXT(bp, 0);
SET_PREV(bp, 0);
return;
}
char* search_ptr;
for (search_ptr = free_listp; search_ptr; search_ptr = GET_NEXT(search_ptr)) {
if (!GET_NEXT(search_ptr)) {
if (search_ptr < bp) {
SET_NEXT(search_ptr, bp);
SET_PREV(bp, search_ptr);
SET_NEXT(bp, 0);
break;
}
}
if (search_ptr > bp) {
if (!GET_PREV(search_ptr)) {
SET_NEXT(bp, search_ptr);
SET_PREV(search_ptr, bp);
SET_PREV(bp, 0);
free_listp = bp;
break;
} else {
char* prev_bp = GET_PREV(search_ptr);
SET_NEXT(bp, search_ptr);
SET_PREV(search_ptr, bp);
SET_PREV(bp, prev_bp);
SET_NEXT(prev_bp, bp);
break;
}
}
}
}
评估¶
s10211900416@JupyterHub:~/malloc1$ ./mdriver -v -t ./traces
Team Name:Tommy
Member 1 :Tommy:10211900416@stu.ecnu.edu.cn
Using default tracefiles in ./traces/
Measuring performance with gettimeofday().
Results for mm malloc:
trace valid util ops secs Kops
0 yes 99% 5694 0.000215 26447
1 yes 99% 5848 0.000196 29837
2 yes 99% 6648 0.000263 25278
3 yes 100% 5380 0.000232 23240
4 yes 66% 14400 0.000189 76030
5 yes 92% 4800 0.003580 1341
6 yes 92% 4800 0.003636 1320
7 yes 55% 12000 0.048982 245
8 yes 51% 24000 0.198017 121
9 yes 27% 14401 0.074155 194
10 yes 34% 14401 0.002708 5319
Total 74% 112372 0.332174 338
Perf index = 44 (util) + 23 (thru) = 67/100
结果比较有戏剧性，改了之后分数还显著下降了/捂脸
空间利用率涨了一点点，但是吞吐量却明显地下降了。
版本三¶
看来显式空闲链表的优化已经到头，为了进一步地优化，我只能搬出来大杀器---分离空闲链表了。
之前看过一些资料，是这样描述分离空闲链表的呢
1 分离适配方法在内存分配中较为常见
2 C标准库中提供的GNU malloc包就是采用的这种方法
3 该方法较为快速，且对内存的使用很有效率
较小的初始块大小¶
相比于课本上给出的实现，我选择了更小的初始堆大小。当内存分配的请求之需要较少的内存时能较好地提高空间利用率。
按大小类的块大小来组织分离空闲链表¶
按照大小类的块大小来组织分离空闲链表会增加插入空闲块到空闲链表操作的时间复杂度，但会使搜索适配块的时候，使用首次适配的效果基本等同于最佳适配，该优化策略能提高空间利用率。
按照请求空间大小分割块¶
通常当适配块的大小大于内存分配请求的大小时，需要我们对适配块进行分割。如果分割的大小不均，会影响空闲块的合并。该优化策略设定一个阀值，根据内存请求的大小来选择将分割后的前半部分或后半部分分配给内存请求，从而减少了内部碎片，提高了空间利用率。
realloc时先检查附近的空闲块¶
通过realloc时先检查临近的空闲块和尝试通过扩展堆大小来满足realloc的大小，从而减少对于mm_alloc的调用，减少内部碎片，提高空间利用率。
所有的代码&评估¶
//版本三
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include "memlib.h"
#include "mm.h"
/* 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)))
#define WSIZE 4
#define DSIZE 8
#define INITSIZE (1 << 6)
#define CHUNKSIZE (1 << 12) /* Extend heap by this amount (bytes) */
#define MINBLOCKSIZE 2 * DSIZE
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define PACK(size, alloc) \
((size) | (alloc)) /* Pack a size and allocated bit into a word */
#define GET(p) (*(unsigned int*)(p)) /* read a word at address p */
#define PUT(p, val) \
(*(unsigned int*)(p) = (val)) /* write a word at address p */
#define GET_SIZE(p) (GET(p) & ~0x7) /* read the size field from address p */
#define GET_ALLOC(p) (GET(p) & 0x1) /* read the alloc field from address p */
/* given block ptr bp, compute address of its header */
#define HDRP(bp) ((char*)(bp)-WSIZE)
/* given block ptr bp, compute address of its footer */
#define FTRP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* given block ptr bp, compute address of next blocks */
#define NEXT_BLKP(bp) ((char*)(bp) + GET_SIZE(HDRP(bp)))
/* given block ptr bp, compute address of prev blocks */
#define PREV_BLKP(bp) ((char*)(bp)-GET_SIZE((char*)(bp)-DSIZE))
/*useful macro definition related to explicit free lists*/
/* next pointer and pre pointer both take up 32 bits */
#define GET_PREV(bp) (*(unsigned int*)(bp))
#define SET_PREV(bp, addr) (*(unsigned int*)(bp) = (addr))
#define GET_NEXT(bp) (*((unsigned int*)(bp) + 1))
#define SET_NEXT(bp, addr) (*((unsigned int*)(bp) + 1) = (addr))
#define LISTCOUNT 16
static char* heap_listp;
static char* separated_free_lists[LISTCOUNT];
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_node(void* bp);
static void delete_node(void* bp);
int mm_init(void);
void* mm_malloc(size_t size);
void mm_free(void* bp);
void* mm_realloc(void* ptr, size_t size);
static void insert_node(void* bp) {
int index = 0;
char* search_ptr = NULL;
char* insert_ptr = NULL;
size_t size = GET_SIZE(HDRP(bp));
while ((index < LISTCOUNT - 1) && (size > 1)) {
size >>= 1;
index++;
}
search_ptr = separated_free_lists[index];
while ((search_ptr != NULL) && (size > GET_SIZE(HDRP(search_ptr)))) {
insert_ptr = search_ptr;
search_ptr = (char*)GET_NEXT(search_ptr);
}
if (search_ptr != NULL) {
if (insert_ptr != NULL) {
char* prev_ptr = GET_PREV(search_ptr);
SET_NEXT(bp, search_ptr);
SET_PREV(search_ptr, bp);
SET_NEXT(prev_ptr, bp);
SET_PREV(bp, prev_ptr);
} else {
SET_NEXT(bp, search_ptr);
SET_PREV(search_ptr, bp);
SET_PREV(bp, 0);
separated_free_lists[index] = bp;
}
} else {
if (insert_ptr != NULL) {
SET_PREV(bp, search_ptr);
SET_NEXT(search_ptr, bp);
SET_NEXT(bp, 0);
} else {
SET_NEXT(bp, 0);
SET_PREV(bp, 0);
separated_free_lists[index] = bp;
}
}
}
static void delete_node(void* bp) {
int index = 0;
size_t size = GET_SIZE(HDRP(bp));
while ((index < LISTCOUNT - 1) && (size > 1)) {
size >>= 1;
index++;
}
char* prev_ptr = GET_PREV(bp);
char* next_ptr = GET_NEXT(bp);
if (prev_ptr) {
if (next_ptr) {
SET_NEXT(prev_ptr, next_ptr);
SET_PREV(next_ptr, prev_ptr);
} else {
SET_NEXT(prev_ptr, 0);
}
} else {
if (next_ptr) {
SET_PREV(next_ptr, 0);
separated_free_lists[index] = next_ptr;
} else {
SET_NEXT(bp, 0);
SET_PREV(bp, 0);
separated_free_lists[index] = NULL;
}
}
}
team_t team = {
/* Team name */
"Tommy",
/* First member's full name */
"Tommy",
/* First member's email address */
"10211900416@stu.ecnu.edu.cn",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""};
/*
* extend heap by words * word(4 bytes)
*/
static void* extend_heap(size_t words) {
char* bp;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1) return NULL;
/* Initialize free block header/footer and the epilogue header */
PUT(HDRP(bp), PACK(size, 0)); // free block header
PUT(FTRP(bp), PACK(size, 0)); // free block footer
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); // new epilogue header
return coalesce(bp); // coalesce if the previous block was free
}
static void* coalesce(void* bp) {
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
void* prev_bp = PREV_BLKP(bp);
void* next_bp = NEXT_BLKP(bp);
if (prev_alloc && next_alloc) {
} else if (prev_alloc && !next_alloc) {
delete_node(next_bp);
size += GET_SIZE(HDRP(next_bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
} else if (!prev_alloc && next_alloc) {
delete_node(prev_bp);
size += GET_SIZE(HDRP(prev_bp));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = prev_bp;
} else {
delete_node(next_bp);
delete_node(prev_bp);
size += GET_SIZE(HDRP(prev_bp)) + GET_SIZE(FTRP(next_bp));
PUT(HDRP(prev_bp), PACK(size, 0));
PUT(FTRP(next_bp), PACK(size, 0));
bp = prev_bp;
}
insert_node(bp);
return bp;
}
static void* find_fit(size_t asize) {
int size = asize;
int index = 0;
void* ptr = NULL;
while (index < LISTCOUNT) {
if ((asize <= 1) && (separated_free_lists[index] != NULL)) {
ptr = separated_free_lists[index];
while ((ptr != NULL) && (size > GET_SIZE(HDRP(ptr)))) {
ptr = (void*)GET_NEXT(ptr);
}
if (ptr != NULL) {
break;
}
}
asize >>= 1;
index++;
}
return ptr;
}
static void* place(void* bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
delete_node(bp);
if ((csize - asize) < MINBLOCKSIZE) {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
return bp;
} else if (asize >= 96) {
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(asize, 1));
PUT(FTRP(NEXT_BLKP(bp)), PACK(asize, 1));
insert_node(bp);
return NEXT_BLKP(bp);
} else {
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
void* next_ptr = NEXT_BLKP(bp);
PUT(HDRP(next_ptr), PACK(csize - asize, 0));
PUT(FTRP(next_ptr), PACK(csize - asize, 0));
insert_node(next_ptr);
return bp;
}
}
int mm_init(void) {
int index;
for (index = 0; index < LISTCOUNT; index++) {
separated_free_lists[index] = NULL;
}
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void*)-1) return -1;
PUT(heap_listp, 0); // alignment padding
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // prologue header
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // prologue footer
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // epilogue header
heap_listp += (2 * WSIZE);
if (extend_heap(INITSIZE / WSIZE) == NULL) return -1;
return 0;
}
void* mm_malloc(size_t size) {
size_t asize; // adjusted block size
size_t extendsize; // amount to extend heap if no fit
char* bp;
if (size == 0) return NULL;
// adjusted block size to include overhead and alignment reqs
if (size <= DSIZE)asize = 2 * DSIZE;
else asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
if ((bp = find_fit(asize)) != NULL) {
return place(bp, asize);
}
// no fit found, get more memory and place the block
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL) return NULL;
return place(bp, asize);
}
void mm_free(void* bp) {
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
void* mm_realloc(void* ptr, size_t size) {
void* new_ptr = ptr;
int remainder;
if (size == 0) return NULL;
if (size <= DSIZE) {
size = 2 * DSIZE;
} else {
size = ALIGN(size + DSIZE);
}
if ((remainder = GET_SIZE(HDRP(ptr)) - size) >= 0) {
return ptr;
} else if (!GET_ALLOC(HDRP(NEXT_BLKP(ptr))) || !GET_SIZE(HDRP(NEXT_BLKP(ptr)))) {
if ((remainder = GET_SIZE(HDRP(ptr)) + GET_SIZE(HDRP(NEXT_BLKP(ptr))) - size) < 0) {
if (extend_heap(MAX(-remainder, CHUNKSIZE) / WSIZE) == NULL) {
return NULL;
}
remainder += MAX(-remainder, CHUNKSIZE);
}
delete_node(NEXT_BLKP(ptr));
PUT(HDRP(ptr), PACK(size + remainder, 1));
PUT(FTRP(ptr), PACK(size + remainder, 1));
} else {
new_ptr = mm_malloc(size);
memcpy(new_ptr, ptr, GET_SIZE(HDRP(ptr)));
mm_free(ptr);
}
return new_ptr;
}
s10211900416@JupyterHub:~/malloc1$ ./mdriver -v -t ./traces
Team Name:Tommy
Member 1 :Tommy:10211900416@stu.ecnu.edu.cn
Using default tracefiles in ./traces/
Measuring performance with gettimeofday().
Results for mm malloc:
trace valid util ops secs Kops
0 yes 97% 5694 0.000283 20120
1 yes 99% 5848 0.000272 21500
2 yes 99% 6648 0.000328 20287
3 yes 99% 5380 0.000267 20142
4 yes 99% 14400 0.000325 44308
5 yes 94% 4800 0.000355 13506
6 yes 91% 4800 0.000354 13548
7 yes 95% 12000 0.000389 30872
8 yes 88% 24000 0.002687 8933
9 yes 99% 14401 0.000207 69469
10 yes 98% 14401 0.000180 79917
Total 96% 112372 0.005647 19898
Perf index = 58 (util) + 40 (thru) = 98/100
wow!看来自己草拟的修改方案是正确的!!!
这个分数是自己达到的最高分数了，后来无论怎样修改都达不到满分了/捂脸
实验感想¶
这次实验感觉最难的是调试。虽然给定的一系列宏可以便利书写程序，但是真心增大了程序的调试难度。
整体而言，先不追求什么效率，先把版本一粗浅地实现后，之后的更改就容易地多了---只需要根据课本上的理论指导修改几个函数即可。
通过这次实验，自己对动态内存分配有了更直观的理解。在这之前，自己第九章学得并不是很明白，因为虚拟内存虽然广为应用，但是又和应用层有些距离。