CMU 15-213 Lab6 Malloc Lab
这次回顾Malloc Lab，主要对课本上的版本进行简单修改。
课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html
课程资料：https://github.com/EugeneLiu/translationCSAPP
课程视频：https://www.bilibili.com/video/av31289365/
参考资料：
- /vm/malloc/mm.c
- https://blog.csdn.net/qq_32693119/article/details/80535662
- https://zhuanlan.zhihu.com/p/150100073
- https://github.com/quanvuong/CSAPP-Malloc-Lab
- https://dreamanddead.github.io/CSAPP-3e-Solutions/chapter9/9.18/
- https://github.com/DreamAndDead/CSAPP-3e-Solutions/blob/gh-pages/chapter9/code/vm/mm.9.18.c
准备工作
完成该lab需要完全理解9.9.12。
报错1：
/usr/include/stdio.h:27:10: fatal error: bits/libc-header-start.h: No such file or directory
#include <bits/libc-header-start.h>解决方法：
apt-get install gcc-multilib报错2：
没有tracefiles文件，可以在如下地址下载：
报错3：
./mdriver -V
Testing mm malloc
Reading tracefile: amptjp-bal.rep
Could not open /afs/cs/project/ics2/im/labs/malloclab/traces/amptjp-bal.rep in read_trace: No such file or directory修改config.h中TRACEDIR为自己的TRACEDIR。
运行方式：
make && ./mdriver -V宏说明
/* Pack a size and allocated bit into a word */
// #define PACK(size, alloc) ((size) | (alloc)) //line:vm:mm:pack
// 第一位记录是否alloc, 第二位记录前一个位置是否alloc
#define PACK(size, alloc, prev_alloc) ((size) | (alloc) | ((prev_alloc) << 1)) //line:vm:mm:pack
// 获得第二位, 判断前一个块是否alloc
#define IS_PREV_ALLOC(p) ((GET(p) >> 1) & 0x1)由于内存块是按字节对齐的，所以最后三位为0，利用最后一位标记当前内存块是否alloc，倒数第二位标记前一个内存卡是否alloc。
/* Read and write a word at address p */
#define GET(p) (*(unsigned int *)(p)) //line:vm:mm:get
#define PUT(p, val) (*(unsigned int *)(p) = (val)) //line:vm:mm:put
/* Read the size and allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7) //line:vm:mm:getsize
#define GET_ALLOC(p) (GET(p) & 0x1) //line:vm:mm:getallocGET获得头部（4字节），PUT设置头部4字节，头部前三个字节记录块大小。
说明：
- 块大小包括首部尾部；
/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char *)(bp) - WSIZE) //line:vm:mm:hdrp
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) //line:vm:mm:ftrp
/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) //line:vm:mm:nextblkp
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) //line:vm:mm:prevblkpbp指向有效载荷的第一位，HDRP指向head的位置，FTRP指向foot的位置，NEXT_BLKP指向后一个块的bp位置，PREV_BLKP指向前一个块的bp位置。
/* Global variables */
static char *heap_listp = 0; /* Pointer to first block */
static char *rover; /* Next fit rover */heap_listp指向第一个块，rover指向前一次内存分配的位置。
代码说明
辅助函数：
static void *extend_heap(size_t words);
static void place(void *bp, size_t asize);
static void *find_fit(size_t asize);
static void *coalesce(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);该版本实现的功能如下：
- 下一次适配；
- 空闲块需要脚部，已分配块只需要头部，见9.9.11；
mm_init
初始化函数，注意对齐块，序言块和结尾块：
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void) {
// 填充字(WSIZE) + 序言块(2*WSIZE) + 结尾块(WSIZE)
// 如果产生错误, 则返回-1
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1){
return -1;
}
// 对齐块
PUT(heap_listp, 0);
// 序言块
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1, 1));
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1, 1));
// 结尾块
PUT(heap_listp + (3 * WSIZE), PACK(0, 1, 1));
// 指向第二个序言块
heap_listp += (2 * WSIZE);
rover = heap_listp;
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) {
return -1;
}
return 0;
}mm_malloc
size指有效载荷大小，注意申请空间时需要头部尾部：
void *mm_malloc(size_t size) {
size_t asize;
size_t extendsize;
char *bp;
// 第一次malloc
if (heap_listp == 0) {
mm_init();
}
// 忽略空申请
if (size == 0) {
return NULL;
}
if (size <= WSIZE) {
// head + content + 8字节对齐
// 4 + 4
asize = DSIZE;
}else {
// head + 8字节对齐
asize = DSIZE * ((size + (WSIZE) + (DSIZE - 1)) / DSIZE);
}
// head + foot + 对齐
// asize = DSIZE + DSIZE * ((size + (DSIZE - 1)) / DSIZE);
// 如果没找到合适的块, 则申请额外空间
if ((bp = find_fit(asize)) == NULL) {
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) {
if (bp == 0) {
return;
}
size_t size = GET_SIZE(HDRP(bp));
// 如果为空则申请
if (heap_listp == 0) {
mm_init();
}
// 更新cur bp
PUT(HDRP(bp), PACK(size, 0, IS_PREV_ALLOC(HDRP(bp))));
PUT(FTRP(bp), PACK(size, 0, IS_PREV_ALLOC(HDRP(bp))));
// 更新next bp
void *next = NEXT_BLKP(bp);
size_t next_size = GET_SIZE(HDRP(next));
if (GET_ALLOC(HDRP(next))) {
// 注意alloc没有foot
PUT(HDRP(next), PACK(next_size, 1, 0));
}else {
PUT(HDRP(next), PACK(next_size, 0, 0));
PUT(FTRP(next), PACK(next_size, 0, 0));
}
coalesce(bp);
}mm_realloc
参考课本的realloc：
void *mm_realloc(void *ptr, size_t size) {
size_t oldsize;
void *newptr;
if (ptr == NULL) {
return mm_malloc(size);
}
if (size == 0) {
mm_free(ptr);
return 0;
}
newptr = mm_malloc(size);
/* If realloc() fails the original block is left untouched */
if(!newptr) {
return 0;
}
/* Copy the old data. */
oldsize = GET_SIZE(HDRP(ptr));
if(size < oldsize) {
oldsize = size;
}
memcpy(newptr, ptr, oldsize);
/* Free the old block. */
mm_free(ptr);
return newptr;
}extend_heap
// 给heap扩充空闲块, 返回块指针
static void *extend_heap(size_t words) {
char *bp;
size_t size;
// 2字对齐
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
// 扩充失败
if ((bp = mem_sbrk(size)) == (void *)-1){
return NULL;
}
// 更新head, foot
PUT(HDRP(bp), PACK(size, 0, IS_PREV_ALLOC(HDRP(bp))));
PUT(FTRP(bp), PACK(size, 0, IS_PREV_ALLOC(HDRP(bp))));
// 更新结尾块
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1, 0));
// 合并块
return coalesce(bp);
}coalesce
参考课本的函数即可，这里对prev_alloc进行了修改：
// 合并块, 返回合并后的指针
static void *coalesce(void *bp) {
// size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t prev_alloc = IS_PREV_ALLOC(HDRP(bp));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
// free的前面为alloc
if (prev_alloc && next_alloc) { // afa
return bp;
}else if (prev_alloc && (!next_alloc)) { // aff
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0, 1));
PUT(FTRP(bp), PACK(size, 0, 1));
}else if ((!prev_alloc) && next_alloc) { // ffa
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0, 1));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0, 1));
bp = PREV_BLKP(bp);
}else { // fff
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0, 1));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0, 1));
bp = PREV_BLKP(bp);
}
// 更新下一次适配的指针
if ((rover > (char *)bp) && (rover < NEXT_BLKP(bp))) {
rover = bp;
}
return bp;
}find_fit
// 下一次适配
static void *find_fit(size_t asize) {
char *oldrover = rover;
// 从上次匹配的地址开始找
for ( ; GET_SIZE(HDRP(rover)) > 0; rover = NEXT_BLKP(rover)) {
if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover)))) {
return rover;
}
}
// 如果没找到则从头开始
void *bp;
for (rover = heap_listp; rover < oldrover; rover = NEXT_BLKP(rover)) {
if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover)))) {
return rover;
}
}
// 没找到则返回null
return NULL;
}place
// 设置块, 如果块大小大于申请大小 + 2 * DSIZE, 则划分块, 不用设置脚步
static void place(void *bp, size_t asize) {
// 保证csize >= asize
size_t csize = GET_SIZE(HDRP(bp));
// 有问题
if (csize >= asize + (2 * DSIZE)) {
// 划分, 设置剩余部分为未划分
// 标记为alloc, free前面为alloc
PUT(HDRP(bp), PACK(asize, 1, 1));
// PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0, 1));
PUT(FTRP(bp), PACK(csize - asize, 0, 1));
}else {
//
PUT(HDRP(bp), PACK(csize, 1, 1));
void *next_bp = NEXT_BLKP(bp);
size_t size = GET_SIZE(HDRP(next_bp));
PUT(HDRP(next_bp), PACK(size, 1, 1));
// PUT(FTRP(bp), PACK(csize, 1));
}
}实验结果
当前版本：
trace valid util ops secs Kops
0 yes 90% 5694 0.001748 3258
1 yes 92% 5848 0.001267 4616
2 yes 95% 6648 0.004152 1601
3 yes 96% 5380 0.004113 1308
4 yes 66% 14400 0.000156 92072
5 yes 91% 4800 0.004463 1076
6 yes 89% 4800 0.004313 1113
7 yes 55% 12000 0.020264 592
8 yes 51% 24000 0.009431 2545
9 yes 27% 14401 0.124472 116
10 yes 34% 14401 0.002566 5611
Total 71% 112372 0.176945 635
Perf index = 43 (util) + 40 (thru) = 83/100课本版本（首次适配）：
Results for mm malloc:
trace valid util ops secs Kops
0 yes 99% 5694 0.006908 824
1 yes 99% 5848 0.005984 977
2 yes 99% 6648 0.010540 631
3 yes 100% 5380 0.007576 710
4 yes 66% 14400 0.000112128917
5 yes 92% 4800 0.006536 734
6 yes 92% 4800 0.006056 793
7 yes 55% 12000 0.140259 86
8 yes 51% 24000 0.258947 93
9 yes 27% 14401 0.097961 147
10 yes 34% 14401 0.002108 6833
Total 74% 112372 0.542987 207
Perf index = 44 (util) + 14 (thru) = 58/100下一次适配：
Results for mm malloc:
trace valid util ops secs Kops
0 yes 91% 5694 0.001704 3342
1 yes 92% 5848 0.001098 5328
2 yes 95% 6648 0.003192 2083
3 yes 97% 5380 0.003308 1627
4 yes 66% 14400 0.000094153191
5 yes 91% 4800 0.003757 1278
6 yes 89% 4800 0.003610 1330
7 yes 55% 12000 0.014973 801
8 yes 51% 24000 0.007385 3250
9 yes 27% 14401 0.097140 148
10 yes 45% 14401 0.002111 6822
Total 73% 112372 0.138371 812
Perf index = 44 (util) + 40 (thru) = 84/100本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere