文章目录
Lab 总结博客链接
前引
这两天感觉人有点昏 昨天没睡好觉 今天不是很想起来的 结果还是硬生生的被自己拽起来 想着今天要把这个Lab给完成了 这段时间压力有点点大 因为开学到现在 什么 离散 概率 数电 大物一点点都没有学 第十周要考大物半期考试 现在是周六 下周二概率论有个随堂小测 本来没有这个随堂小测的话 我就可以等到期末3周再准备的 = =
好了 也没什么好说的 就是发了点牢骚呜 这两天刷力扣遇到了点瓶颈 这段时间力扣就先放放 等最后把这本《深入理解计算机系统》刷完再恢复刷题了 本来做Lab就累人 刷完题再来做Lab肯定是不行的
不扯这么多了 刚刚才解决了任务初期的编译问题 那我们就直接下面走起吧 我完成了这个Lab后 个人感觉难度不是很难 注意是编译的细节 还有需要调试 调试的方法还有我调试的过程 会在图片与代码中体现 大家继续往下看吧
Lab6 Malloc Lab
1、获取相关Lab材料
老样子吧 贴个CSAPP:3e的链接 大家自己下下来 放到虚拟机上面 解压之后就可以开始了 还要记得去下一哈Write Up 实验文档
Computer Systems: A Programmer’s Perspective, 3/E (CS:APP3e)
2010年版的Lab链接
CSAPP 2010 labs cmu edu
对于2010年版的Lab 我刚刚也去下载试了一下 发现出现了各种问题 比如刚开始就出现的编译问题 - - cc1 all warnings being treated as errors 就算了 还是回到我们的老版本Lab中
还有一点 一定要注意 2001年版的 我们是采用的32位编译模式 不是64位 一定要注意
下面放一哈实验文档截图 我开了会员用的pdf中文翻译了 开会员是感觉 这个比机翻很多地方翻译的好一点 对于细节的地方还是需要去看看原版英文的文档
2、开始Lab前的部分问题解决
1、解决编译问题 libstdc++.so不兼容（更换gcc版本）
没错 又是编译问题 每次我拿到实验开始 我都会先去试着编译一下 make 看看会不会有报错 或者什么库文件缺失
果然 在我刚解压后 去尝试 make编译就发生了下面的错误
（叹息） 没办法 出现问题总得是需要去解决的 我看了看我的编译器版本 因为之前Lab4编译出错过 我换成了低版本的编译器gcc-4.6就解决了 现在又不行了
那我们就老样子 先用sudo update-alternatives --config gcc来看看 但是在我尝试了一番 发现我的新版gcc-9怎么没有出现在可替换项中 其他的gcc都有问题 不兼容
我找了找 我系统原本带的gcc-9就是在/usr/bin/gcc-9中 所以我要把我们的gcc-9给放进去 放到可替换项中 则命令如下
增加link命令（100为优先级权值）
sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-9 100
删除不需要的link命令 （例如 /usr/bin/gcc-9）
sodu update-alternatives --remove gcc /usr/bin/gcc-9
在输入完增加的命令后 我们再看一下备用项sudo update-alternatives --config gcc 果然最底部就多了一条 我们的新版本gcc-9 我们最后再输入其序号4 就更换了版本 最后也就成功完成了编译
2、Traces不完整（提供下载链接 Traces添加进文件夹）
由于最后我们的看我们完成度如何是通过下面的指令来看的./mdriver -V来看我们十个用例的Trace综合测评 所以我们不能缺了那10个Traces 刚好 我们的Lab里面就少了 所以大家把Traces在下面的链接下载放到你的Lab文件夹中
我CSDN也把那10个Trace上传了 大家可以通过第一个链接下载
下载链接
Love 6’s Private Blog CSDN资源提供 Lab6 Malloc Lab 完整Traces
Lab 6 Malloc Lab 完整的 12 traces Github 下载链接
下载完了之后 我们放到自己的文件夹中 或者放在一个自己晓得的路径里面 然后我们去修改config.h
修改文件
config.h第十五行（路径自定）
#define TRACEDIR "/home/cooiboi/CSAPP/malloclab-handout/traces/
最后我们重新编译 make后 试一下./mdriver -V 用的是默认的示例代码 成功运行
3、Start Lab Overview（总览）
1、实验介绍 + 任务分析
好了 在忙完这么久后终于终于可以动手开始做实验了 当然作为老实验人 自然而然需要 先了解实验要让我们干什么 对吧
Malloc Lab我们的任务是模拟c语言函数中的mallocfreerealloc当然我们这个环境是模拟出来的 在完成这个Lab前 强烈建议先认真看完第九章虚拟内存后半部分会讲到很多实现就是关于我们这部分的实验实现 所以我的建议是先看完虚拟内存那一章 再来做Lab
其实在看完书后 很多东西就不需要写了 因为大部分代码 如果你实在没有思路 你就直接抄书上的就行了 我实现的时候 基本上就没有参考过书 因为书上实现的思路看懂了 自己再去实现 很多时候就是按照自己的想法去想了
所以下面的代码没有参照过书上的
我们的任务不仅仅是完成mallocfreerealloc不像是前一个实验 我们完成了就行了 我们这个实验是 完成了函数功能 我们根据空间利用率即有效占用 比如系统分配了200字节 到最后只有100字节是有效的 被占用的 其他100字节根本没被用 还根据运行时间即我们的吞吐量或者而言我们以每次操作的时间复杂度来比较 因为每次寻找malloc合适存放的内存位置如果是线性关系的话 到后面内存越大 那么遍历时间就越久
相反如果每次我们都可以在线性时间找到 并把我们的内存地址发出去 那么时间就会大大的节约 同样因为线性时间发出去 可能我们的空间利用率也会变高 所以我们的任务是 尽可能的完成一个高效 高空间利用率 高性能的malloc lab
当然不可以一口气吃成胖子 实验都是需要从最底层出发 就像linux刚开始从一个一万行代码的操作系统 慢慢发展 优化 改进 到现在的这么高*度 这么强壮的操作系统
所以我们还是耐心点 从最基础的 最简单的malloc实现思路开始 先完成一个基本款的malloc运行监测通过后 我们再继续优化
2、调试方式介绍
我刚开始也是很担心 没有办法调试 但是当我发现老朋友
printf仍然可以使用时 我就知道 之后什么事情都不叫事了
比如我们之后发生了段错误 我们就直接在每个函数那里 加一下想要输出的参数 比如看一下 指针的地址printf（"ptr_address %x\n",(int)ptr）
我们调试的时候 直接运行./mdriver -g或者./mdriver -f filename终端都会输出出来我们在函数中写入的printf
所以这个地方就先写到这里 大家自己去试试 方法已经介绍了 就原来我不放图了
4、正式开始实验编写
1、Basic Version 1.0（隐式空闲列表）
这个版本的思路 就是最基本的
malloc线性寻找 从头部开始搜寻 找到即返回free合并思路while先向上回收 再向下回收realloc就按照函数的原意来写就行了
那就不多加解释了 下面这里有个问题
大家可以想一下 这里我调试调了半个小时 如果p不加上() 那么就会导致错误 代码如下 写出来就是希望大家注意一下这样的 小问题
#define GET_WORD(p) (*((int*)(p)))
#define GET_WORD(p) (*((int*)p))
GET_WORD(blk_ptr - WORD_SIZE)
代码如下 大家直接看咯
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team = {
/* Team name */
"Love6 Team",
/* First member's full name */
" Love6 qvq\nBlogs Website",
/* First member's email address */
" https://love6.blog.csdn.net",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""
};
#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WORD_SIZE (4) // Word 4 bytes
#define DWORD_SIZE (8) // Double Word 8 bytes
#define CHUNKSIZE (1 << 12) // (1 << 12) = 4096
#define MAX(x,y) ((x >= y) ? (x) : (y)) // max
#define MIN(x,y) ((x <= y) ? (x) : (y)) // min
#define PACK_SIZE_ALLOC(size,alloc) (size | alloc) // 3 for alloc,29 for size
#define GET_WORD(p) (*((int*)(p))) // unsigned int 4 bytes
#define PUT_WORD(p,val) ((*((int*)(p))) = val) // put val
#define GET_SIZE(blk_ptr) (GET_WORD((void*)blk_ptr - WORD_SIZE) & ~0x7) //(~0x7 = (111..29 bits) + (000..3bits))
#define GET_ALLOC(blk_ptr) (GET_WORD((void*)blk_ptr - WORD_SIZE) & 0x1) // 0 unused 1 used
#define GET_VALID_SIZE(blk_ptr) (GET_SIZE(blk_ptr) - 0x8)
#define HEADER_PTR(blk_ptr) ((void*)blk_ptr - WORD_SIZE) // Header 4 bytes
#define FOOTER_PTR(blk_ptr) ((void*)blk_ptr + GET_SIZE(blk_ptr) - DWORD_SIZE) // BLK_PTR + malloced bytes = Footer_Ptr
#define PUT_HEADER_WORD(blk_ptr,size,alloc) PUT_WORD(HEADER_PTR(blk_ptr),PACK_SIZE_ALLOC(size,alloc)) // FOR CONVENIENCE
#define PUT_FOOTER_WORD(blk_ptr,size,alloc) PUT_WORD(FOOTER_PTR(blk_ptr),PACK_SIZE_ALLOC(size,alloc)) // FOR CONVENIENCE
#define NEXT_BLOCK_PTR(blk_ptr) ((void*)blk_ptr + GET_SIZE(blk_ptr)) // NEXT_BLOCK_PTR = BLK_PTR + SIZE
#define PREV_BLOCK_PTR(blk_ptr) ((void*)blk_ptr - GET_SIZE((blk_ptr - WORD_SIZE))) // PREV_BLOCK_PTR = BLK_PTR - PREV_SIZE
#define ROUNDUP_EIGHT_BYTES(size) (((size + (DWORD_SIZE - 1)) / 8) * 8) // ROUND FOR EVERY 8 BYTES
static void* heap_list = NULL;
/*
* extend_heap - heap_mem needed to be larger extend_word_size bytes
*/
static void* extend_heap(size_t extend_word_size)
{
void* blk_ptr = NULL;
size_t size;
size = (extend_word_size % 2) ? (extend_word_size + 1) * WORD_SIZE : extend_word_size * WORD_SIZE;
if((blk_ptr = mem_sbrk(size)) == (void*)-1)
return NULL;
PUT_HEADER_WORD(blk_ptr,size,0);
PUT_FOOTER_WORD(blk_ptr,size,0);
PUT_WORD(FOOTER_PTR(blk_ptr) + WORD_SIZE,PACK_SIZE_ALLOC(0,0));
return blk_ptr;
}
static void* find_fit_block_ptr(size_t size)
{
void* blk_ptr = heap_list + DWORD_SIZE,*heap_hi_address = mem_heap_hi();
while(blk_ptr < heap_hi_address)
{
if(!GET_ALLOC(blk_ptr) && GET_SIZE(blk_ptr) >= size)
return blk_ptr;
blk_ptr = NEXT_BLOCK_PTR(blk_ptr);
}
return NULL;
}
static void place(void* blk_ptr,size_t size)
{
size_t prev_size = GET_SIZE(blk_ptr),now_size = prev_size - size;
PUT_HEADER_WORD(blk_ptr,size,1);
PUT_FOOTER_WORD(blk_ptr,size,1);
//printf("place in,now size:%d,blk:%x,pre_one size:%x,pre_add :%x\n",GET_SIZE(blk_ptr),(int)blk_ptr,GET_WORD(HEADER_PTR(blk_ptr) - WORD_SIZE),PREV_BLOCK_PTR(blk_ptr));
if(!now_size) return;
void* next_ptr = NEXT_BLOCK_PTR(blk_ptr);
//printf("place has empty space,empty_one size:%d,blk:%x\n",now_size,(int)(next_ptr));
PUT_HEADER_WORD(next_ptr,now_size,0);
PUT_FOOTER_WORD(next_ptr,now_size,0);
}
static void merge_free_fragment(void* ptr)
{
// Front_block Used Behind_block Used - DOING NOTING
void* prev_ptr,*next_ptr,*now_ptr,*heap_hi_address = mem_heap_hi();
if(ptr > heap_list && GET_ALLOC(PREV_BLOCK_PTR(ptr)) && (NEXT_BLOCK_PTR(ptr) > heap_hi_address || GET_ALLOC(NEXT_BLOCK_PTR(ptr))))
return;
// Merge Free Front_blocks
now_ptr = ptr;
prev_ptr = PREV_BLOCK_PTR(now_ptr);
//printf("merge free now_ptr: %x prev_ptr: %x\n",(int)now_ptr,(int)prev_ptr);
while(prev_ptr > heap_list && !GET_ALLOC(prev_ptr))
{
size_t sum_size = GET_SIZE(now_ptr) + GET_SIZE(prev_ptr);
PUT_FOOTER_WORD(now_ptr,sum_size,0);
PUT_HEADER_WORD(prev_ptr,sum_size,0);
now_ptr = prev_ptr;
prev_ptr = PREV_BLOCK_PTR(prev_ptr);
}
// Merge Free Behind_blocks
next_ptr = NEXT_BLOCK_PTR(ptr);
while(next_ptr < heap_hi_address && !GET_ALLOC(next_ptr))
{
size_t sum_size = GET_SIZE(now_ptr) + GET_SIZE(next_ptr);
PUT_HEADER_WORD(now_ptr,sum_size,0);
PUT_FOOTER_WORD(next_ptr,sum_size,0);
next_ptr = NEXT_BLOCK_PTR(next_ptr);
}
return;
}
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
if((heap_list = mem_sbrk(4 * WORD_SIZE)) == (void*)-1)
return -1;
PUT_WORD(heap_list,PACK_SIZE_ALLOC(0,0));
PUT_WORD(heap_list + 1 * WORD_SIZE,PACK_SIZE_ALLOC(8,1)); // first two blocks start (8/1)
PUT_WORD(heap_list + 2 * WORD_SIZE,PACK_SIZE_ALLOC(8,1)); // first two blocks end (8/1)
PUT_WORD(heap_list + 3 * WORD_SIZE,PACK_SIZE_ALLOC(0,1)); // end one block end (0/1)
heap_list += (2 * WORD_SIZE); // heap_list = (8/1)
if(extend_heap(CHUNKSIZE / WORD_SIZE) == 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)
{
if(!size) return NULL;
void* blk_ptr = NULL;
// ROUND_UP_FOR EVERY EIGHT BYTE + HEADER_FOOTER_COST
size = ROUNDUP_EIGHT_BYTES(size) + 8;
// can find fited_block
if((blk_ptr = find_fit_block_ptr(size)) != NULL)
{
place(blk_ptr,size);
//printf("malloc fit size :%d,blk_ptr: %x\n",size,(int)blk_ptr);
return blk_ptr;
}
// extend heap
blk_ptr = extend_heap(MAX(CHUNKSIZE,size) / WORD_SIZE);
if(!blk_ptr) return NULL;
//printf("malloc extend_heap,blk: %x\n",(int)blk_ptr);
place(blk_ptr,size);
return blk_ptr;
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *ptr)
{
//not allowed free
if(ptr == NULL || ptr <= heap_list || ptr >= mem_heap_hi())
return;
PUT_HEADER_WORD(ptr,GET_SIZE(ptr),0);
PUT_FOOTER_WORD(ptr,GET_SIZE(ptr),0);
//printf("free size :%d blk_ptr: %x prev_size: %x\n",GET_SIZE(ptr),(int)ptr,GET_SIZE((void*)ptr - DWORD_SIZE));
merge_free_fragment(ptr);
return;
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
void *newptr;
if(!size)
{
mm_free(ptr);
return NULL;
}
newptr = mm_malloc(size);
if(!ptr || !newptr) return newptr;
size_t copy_size = MIN(size,GET_VALID_SIZE(ptr));
memcpy(newptr,ptr,copy_size);
mm_free(ptr);
return newptr;
}
1、Results For Version 1.0（60 scores）
当10个traces 终于全对时 我其实没有太在意分数 因为全程我基本上都没有看过书 都是凭着自己原来看过书的记忆 模模糊糊记忆来写的
但显然 60的scores 我们并没有那么满意 刚好及格 但是万事开头难 之后再在Version 1.0的迭代 就没有那么困难了 那我们趁着势头 继续往下走
2、Basic Version 2.0（隐式显式双向链表 + 分离适配）
经过了缜密的分析与稍加修改 我们的第二版比我预想的要快就出炉了 经过测试 效果比原来的好得多 可以说 这个已经可以作为最终版本啦
当然 也是没有怎么看其他的代码 自己写出来的
刚开始的前两个小时 我基本上把之前的所有函数都删除了 然后从零开始写 因为我觉得需要 需要双向链表 就不可能像之前那样了 还增加了许许多多的函数和宏定义
在那两个小时中 我删删改改 磕磕碰碰 总是觉得哪里不对劲 之后又重新打开书 想再仔细研究研究 因为对于最后free的合并 没有什么思路 而之后我看到了这个图之后 所有的一切都变得简单了 吃完午饭 回来 我按照这个图的结构摆放设计 多花了一个多小时 最后的成品就出了
图如下
对的 中间隔了一个分界线 就是希望如果你没有思路的话 看到上面的图 右边的 就应该明白怎么去完成这个Lab了 建议好好思考一下
那我们这里就直接开始讲思路了Basic Version 1.0的代码其实已经完成了相当大部分的任务了 我们最后只需要再加上一个双向链表即可 我的双向链表 大小类区分是以2的幂来进行区分的 通俗点就是1-12-34-78-15这样来设计的 因为我们的堆最大需要支持4GB所以我们需要数组大小为32位的 双向链表
双向链表的个数解决了 那我们的malloc需要多加什么呢 不需要多加什么 因为搜寻工作 我们已经交给双向链表了我们每次通过看size在哪个大小类区间 从而寻找相对应的块 如果不存在 则向上一位 继续寻找 直到找到或者找到链表数组最后一位 如果都没有满足的 我们就直接 向外申请内存 填进来malloc需要注意的不多 其实稍微难一点的就是free合并放块 其实都不是很难 因为上面真的已经完成了绝大部分的工作了 我们唯一需要做的就只是 维护一个双向链表 + 每次找块从部分堆里面找
剩下的好像真的就没什么了 可能这个实验 难度我觉得真的不是很难 - - 就是需要耐心 还有一些细节吧
Basic Version 2.0代码实现如下 大家自己看看啦 里面还有些我的调试记录 我就不删除了 留下来 给大家一点点启发
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <unistd.h>
#include <string.h>
#include "mm.h"
#include "memlib.h"
/*********************************************************
* NOTE TO STUDENTS: Before you do anything else, please
* provide your team information in the following struct.
********************************************************/
team_t team = {
/* Team name */
"Love6 Team",
/* First member's full name */
" Love6 qvq\nBlogs Website",
/* First member's email address */
" https://love6.blog.csdn.net",
/* Second member's full name (leave blank if none) */
"",
/* Second member's email address (leave blank if none) */
""
};
#define ALIGNMENT 8
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WORD_SIZE (4) // Word 4 bytes
#define DWORD_SIZE (8) // Double Word 8 bytes
#define CHUNKSIZE (1 << 12) // (1 << 12) = 4096
#define MAX(x,y) ((x >= y) ? (x) : (y)) // max
#define MIN(x,y) ((x <= y) ? (x) : (y)) // min
#define PACK_SIZE_ALLOC(size,alloc) (size | alloc) // 3 for alloc,29 for size
#define GET_WORD(p) (*((int*)(p))) // unsigned int 4 bytes
#define PUT_WORD(p,val) ((*((int*)(p))) = val) // put val
#define GET_SIZE(blk_ptr) (GET_WORD((void*)blk_ptr - WORD_SIZE) & ~0x7) //(~0x7 = (111..29 bits) + (000..3bits))
#define GET_ALLOC(blk_ptr) (GET_WORD((void*)blk_ptr - WORD_SIZE) & 0x1) // 0 unused 1 used
#define GET_VALID_SIZE(blk_ptr) (GET_SIZE(blk_ptr) - 0x8)
#define HEADER_PTR(blk_ptr) ((void*)blk_ptr - WORD_SIZE) // Header 4 bytes
#define FOOTER_PTR(blk_ptr) ((void*)blk_ptr + GET_SIZE(blk_ptr) - DWORD_SIZE) // BLK_PTR + malloced bytes = Footer_Ptr
#define PUT_HEADER_WORD(blk_ptr,size,alloc) PUT_WORD(HEADER_PTR(blk_ptr),PACK_SIZE_ALLOC(size,alloc)) // FOR CONVENIENCE
#define PUT_FOOTER_WORD(blk_ptr,size,alloc) PUT_WORD(FOOTER_PTR(blk_ptr),PACK_SIZE_ALLOC(size,alloc)) // FOR CONVENIENCE
#define PUT_PREV_PTR_WORD(blk_ptr,address) PUT_WORD(blk_ptr,address)
#define PUT_NEXT_PTR_WORD(blk_ptr,address) PUT_WORD(blk_ptr + WORD_SIZE,address)
#define NEXT_BLOCK_PTR(blk_ptr) ((void*)blk_ptr + GET_SIZE(blk_ptr)) // NEXT_BLOCK_PTR = BLK_PTR + SIZE
#define PREV_BLOCK_PTR(blk_ptr) ((void*)blk_ptr - GET_SIZE((blk_ptr - WORD_SIZE))) // PREV_BLOCK_PTR = BLK_PTR - PREV_SIZE
#define ROUNDUP_EIGHT_BYTES(size) (((size + (DWORD_SIZE - 1)) / 8) * 8) // ROUND FOR EVERY 8 BYTES
static void* heap_list = NULL;
struct block_node
{
struct block_node* prev_ptr;
struct block_node* next_ptr;
} block_node;
static struct blocks_list_node
{
struct block_node start_node;
struct block_node end_node;
} blocks_list[32];
static size_t size2index(size_t size)
{
size_t tmpsize = 1,index = 0;
while((tmpsize <<= 1) <= size)
++index;
return index;
}
static void init_block_node(struct block_node* block_node)
{
block_node->next_ptr = NULL;
block_node->prev_ptr = NULL;
}
static void init_block_list(struct blocks_list_node* block_list)
{
init_block_node(&block_list->start_node);
init_block_node(&block_list->end_node);
block_list->start_node.next_ptr = (&block_list->end_node);
block_list->end_node.prev_ptr = (&block_list->start_node);
}
static void insert_put_block_ptr(struct blocks_list_node* block_list,void* block_ptr)
{
PUT_WORD(block_ptr,(int)&block_list->start_node);
PUT_WORD(block_ptr + WORD_SIZE,(int)block_list->start_node.next_ptr);
struct block_node* block_node_ptr = (struct block_node*)block_ptr;
block_node_ptr->next_ptr = block_list->start_node.next_ptr;
block_node_ptr->prev_ptr = &block_list->start_node;
block_node_ptr->prev_ptr->next_ptr = block_node_ptr;
block_node_ptr->next_ptr->prev_ptr = block_node_ptr;
//printf("insert blk_node: %x,size: %d\n",(int)block_node_ptr,GET_SIZE(block_ptr));
}
static void remove_block_ptr(void* blk_node)
{
struct block_node* block_ptr = (struct block_node*)blk_node;
//printf("remove blk_node: %x,size: %d\n",(int)block_ptr,GET_SIZE(blk_node));
block_ptr->prev_ptr->next_ptr = block_ptr->next_ptr;
block_ptr->next_ptr->prev_ptr = block_ptr->prev_ptr;
}
/*
* extend_heap - heap_mem needed to be larger extend_word_size bytes
*/
static void* extend_heap(size_t extend_word_size)
{
//printf("extend begin\n");
void* blk_ptr = NULL;
size_t size;
size = (extend_word_size % 2) ? (extend_word_size + 1) * WORD_SIZE : extend_word_size * WORD_SIZE;
if((blk_ptr = mem_sbrk(size)) == (void*)-1)
return NULL;
size_t index = size2index(size);
PUT_HEADER_WORD(blk_ptr,size,0);
PUT_FOOTER_WORD(blk_ptr,size,0);
PUT_WORD(FOOTER_PTR(blk_ptr) + WORD_SIZE,PACK_SIZE_ALLOC(0,0));
insert_put_block_ptr(blocks_list + index,blk_ptr);
//printf("extend end\n");
return blk_ptr;
}
static void* find_fit_block_ptr(size_t index,size_t size)
{
int i;
struct block_node* ptr,*end_ptr;
for(i=index;i<32;++i)
{
ptr = blocks_list[i].start_node.next_ptr;
end_ptr = &blocks_list[i].end_node;
while(ptr != end_ptr)
{
if(GET_SIZE(((void*)ptr)) >= size)
return (void*)ptr;
ptr = ptr->next_ptr;
}
}
return NULL;
}
static void place(void* blk_ptr,size_t size)
{
size_t prev_size = GET_SIZE(blk_ptr),now_size = prev_size - size;
remove_block_ptr(blk_ptr);
if(now_size <= 8)
{
PUT_HEADER_WORD(blk_ptr,prev_size,1);
PUT_FOOTER_WORD(blk_ptr,prev_size,1);
return;
}
PUT_HEADER_WORD(blk_ptr,size,1);
PUT_FOOTER_WORD(blk_ptr,size,1);
void* next_ptr = NEXT_BLOCK_PTR(blk_ptr);
size_t index = size2index(now_size);
PUT_HEADER_WORD(next_ptr,now_size,0);
PUT_FOOTER_WORD(next_ptr,now_size,0);
insert_put_block_ptr(blocks_list + index,next_ptr);
}
static void* merge_free_fragment(void* ptr)
{
// Front_block Used Behind_block Used - DOING NOTING
void* prev_ptr,*next_ptr,*now_ptr,*heap_hi_address = mem_heap_hi();
// Merge Free Front_blocks
now_ptr = ptr;
prev_ptr = PREV_BLOCK_PTR(now_ptr);
//printf("merge free now_ptr: %x prev_ptr: %x\n",(int)now_ptr,(int)prev_ptr);
while(prev_ptr > heap_list && !GET_ALLOC(prev_ptr))
{
size_t sum_size = GET_SIZE(now_ptr) + GET_SIZE(prev_ptr);
PUT_FOOTER_WORD(now_ptr,sum_size,0);
PUT_HEADER_WORD(prev_ptr,sum_size,0);
remove_block_ptr(prev_ptr);
now_ptr = prev_ptr;
prev_ptr = PREV_BLOCK_PTR(prev_ptr);
}
// Merge Free Behind_blocks
next_ptr = NEXT_BLOCK_PTR(ptr);
while(next_ptr < heap_hi_address && !GET_ALLOC(next_ptr))
{
size_t sum_size = GET_SIZE(now_ptr) + GET_SIZE(next_ptr);
PUT_HEADER_WORD(now_ptr,sum_size,0);
PUT_FOOTER_WORD(next_ptr,sum_size,0);
remove_block_ptr(next_ptr);
next_ptr = NEXT_BLOCK_PTR(next_ptr);
}
return now_ptr;
}
/*
* mm_init - initialize the malloc package.
*/
int mm_init(void)
{
if((heap_list = mem_sbrk(4 * WORD_SIZE)) == (void*)-1)
return -1;
PUT_WORD(heap_list,PACK_SIZE_ALLOC(0,0));
PUT_WORD(heap_list + 1 * WORD_SIZE,PACK_SIZE_ALLOC(8,1)); // first two blocks start (8/1)
PUT_WORD(heap_list + 2 * WORD_SIZE,PACK_SIZE_ALLOC(8,1)); // first two blocks end (8/1)
PUT_WORD(heap_list + 3 * WORD_SIZE,PACK_SIZE_ALLOC(0,1)); // end one block end (0/1)
heap_list += (2 * WORD_SIZE); // heap_list = (8/1)
int i;
for(i=0;i<32;++i)
init_block_list(blocks_list + i);
if(extend_heap(CHUNKSIZE / WORD_SIZE) == 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)
{
if(!size) return NULL;
//printf("malloc start\n");
void* blk_ptr = NULL;
// ROUND_UP_FOR EVERY EIGHT BYTE + HEADER_FOOTER_COST
size = ROUNDUP_EIGHT_BYTES(size) + 8;
// can find fited_block
size_t index = size2index(size);
if((blk_ptr = find_fit_block_ptr(index,size)) != NULL)
{
place(blk_ptr,size);
//printf("malloc find end\n");
return blk_ptr;
}
// extend heap
blk_ptr = extend_heap(MAX(CHUNKSIZE,size) / WORD_SIZE);
if(!blk_ptr) return NULL;
//printf("malloc extend_heap,blk: %x\n",(int)blk_ptr);
place(blk_ptr,size);
//printf("malloc extend end\n");
return blk_ptr;
}
/*
* mm_free - Freeing a block does nothing.
*/
void mm_free(void *ptr)
{
//not allowed free
if(ptr == NULL || ptr <= heap_list || ptr >= mem_heap_hi())
return;
PUT_HEADER_WORD(ptr,GET_SIZE(ptr),0);
PUT_FOOTER_WORD(ptr,GET_SIZE(ptr),0);
//printf("free start\n");
ptr = merge_free_fragment(ptr);
//printf("free cant find end\n");
if(!ptr) return;
size_t size = GET_SIZE(ptr),index = size2index(size);
insert_put_block_ptr(blocks_list + index,ptr);
//printf("free end\n");
return;
}
/*
* mm_realloc - Implemented simply in terms of mm_malloc and mm_free
*/
void *mm_realloc(void *ptr, size_t size)
{
void *newptr;
if(!size)
{
mm_free(ptr);
return NULL;
}
newptr = mm_malloc(size);
if(!ptr || !newptr) return newptr;
size_t copy_size = MIN(size,GET_VALID_SIZE(ptr));
memcpy(newptr,ptr,copy_size);
mm_free(ptr);
return newptr;
}
2、Results For Version 2.0（85 scores）
总的来说 85分还是比较满意的 原谅我为什么不写其他稍微差一点性能的malloc 因为有好的 我自然就去写好的了 - - 主要还是人比较懒
还算好 这两天压力比较大 后天概率论有小测 但是现在还没学 我明天开始从零学习 呜呜 今天还好把Lab写完了 不然可能学概率论的事情还得往后放放了
天下没有不散的宴席 这个Lab还是挺好的 我看了看书 我的实现的版本 好像就是GNU的Malloc包的简易版本 哈哈 挺有意思的一次体验
可能后面还有两个实验 因为刚刚去看了看2010年版的 结果发现 文件系统还有一个Lab 那就先写到这啦 各位之后再见啦~