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

素颜马尾好姑娘i 2022-09-17 01:52 478阅读 0赞

### 文章目录 ###

*   *  Lab 总结博客链接
     *  前引
     *  Lab6 Malloc Lab
     *   *  1、获取相关Lab材料
         *  2、开始Lab前的部分问题解决
         *   *  1、解决编译问题 libstdc++.so不兼容（更换gcc版本）
             *  2、Traces不完整（提供下载链接 Traces添加进文件夹）
         *  3、Start Lab Overview（总览）
         *   *  1、实验介绍 + 任务分析
             *  2、调试方式介绍
         *  4、正式开始实验编写
         *   *  1、Basic Version 1.0（隐式空闲列表）
             *  1、Results For Version 1.0（60 scores）
             *  2、Basic Version 2.0（隐式显式双向链表 + 分离适配）
             *  2、Results For Version 2.0（85 scores）
         *  结束图

--------------------

## Lab 总结博客链接 ##

--------------------

**[CSAPP Lab入门系统安装摸索 + Lab 博客链接][CSAPP Lab_ _ 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)][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`中文翻译了 开会员是感觉 这个比机翻很多地方翻译的好一点 对于细节的地方还是需要去看看原版英文的文档**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

### 2、开始Lab前的部分问题解决 ###

--------------------

#### 1、解决编译问题 libstdc++.so不兼容（更换gcc版本） ####

--------------------

**没错 又是编译问题 每次我拿到实验开始 我都会先去试着编译一下 `make` 看看会不会有报错 或者什么库文件缺失**  
**果然 在我刚解压后 去尝试 `make`编译就发生了下面的错误**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 1]

--------------------

**（叹息） 没办法 出现问题总得是需要去解决的 我看了看我的编译器版本 因为之前`Lab4`编译出错过 我换成了低版本的编译器`gcc-4.6`就解决了 现在又不行了**

**那我们就老样子 先用`sudo update-alternatives --config gcc`来看看 但是在我尝试了一番 发现我的新版`gcc-9`怎么没有出现在可替换项中 其他的`gcc`都有问题 不兼容**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 2]

--------------------

**我找了找 我系统原本带的`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` 就更换了版本 最后也就成功完成了编译**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 3]

--------------------

#### 2、Traces不完整（提供下载链接 Traces添加进文件夹） ####

--------------------

**由于最后我们的看我们完成度如何是通过下面的指令来看的**  
**`./mdriver -V`来看我们十个用例的`Trace`综合测评 所以我们不能缺了那10个`Traces` 刚好 我们的`Lab`里面就少了 所以大家把`Traces`在下面的链接下载放到你的`Lab`文件夹中**

**我`CSDN`也把那10个`Trace`上传了 大家可以通过第一个链接下载**

--------------------

**下载链接**  
**[Love 6’s Private Blog CSDN资源提供 Lab6 Malloc Lab 完整Traces][Love 6_s Private Blog CSDN_ Lab6 Malloc Lab _Traces]**  
**[Lab 6 Malloc Lab 完整的 12 traces Github 下载链接][Lab 6 Malloc Lab _ 12 traces Github]**

--------------------

**下载完了之后 我们放到自己的文件夹中 或者放在一个自己晓得的路径里面 然后我们去修改`config.h`**

> **修改文件`config.h`第十五行（路径自定）**  
> **\#define TRACEDIR "/home/cooiboi/CSAPP/malloclab-handout/traces/**

--------------------

**最后我们重新编译 `make`后 试一下`./mdriver -V` 用的是默认的示例代码 成功运行**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 4]

--------------------

### 3、Start Lab Overview（总览） ###

--------------------

#### 1、实验介绍 + 任务分析 ####

--------------------

**好了 在忙完这么久后终于终于可以动手开始做实验了 当然作为老实验人 自然而然需要 先了解实验要让我们干什么 对吧**

> **`Malloc Lab` 我们的任务是模拟c语言函数中的 `malloc` `free` `realloc` 当然我们这个环境是模拟出来的 在完成这个`Lab`前 强烈建议先认真看完第九章`虚拟内存` 后半部分会讲到很多实现就是关于我们这部分的实验实现 所以我的建议是先看完虚拟内存那一章 再来做Lab**  
>   
> **其实在看完书后 很多东西就不需要写了 因为大部分代码 如果你实在没有思路 你就直接抄书上的就行了 我实现的时候 基本上就没有参考过书 因为书上实现的思路看懂了 自己再去实现 很多时候就是按照自己的想法去想了**  
> **所以下面的代码没有参照过书上的**  
>   
> **我们的任务不仅仅是完成`malloc` `free` `realloc` 不像是前一个实验 我们完成了就行了 我们这个实验是 完成了函数功能 我们根据 `空间利用率` 即有效占用 比如系统分配了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`的迭代 就没有那么困难了 那我们趁着势头 继续往下走**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 5]

--------------------

#### 2、Basic Version 2.0（隐式显式双向链表 + 分离适配） ####

--------------------

> **经过了缜密的分析与稍加修改 我们的第二版比我预想的要快就出炉了 经过测试 效果比原来的好得多 可以说 这个已经可以作为最终版本啦**  
> **当然 也是没有怎么看其他的代码 自己写出来的**  
> **刚开始的前两个小时 我基本上把之前的所有函数都删除了 然后从零开始写 因为我觉得需要 需要双向链表 就不可能像之前那样了 还增加了许许多多的函数和宏定义**  
>   
> **在那两个小时中 我删删改改 磕磕碰碰 总是觉得哪里不对劲 之后又重新打开书 想再仔细研究研究 因为对于最后`free`的合并 没有什么思路 而之后我看到了这个图之后 所有的一切都变得简单了 吃完午饭 回来 我按照这个图的结构摆放设计 多花了一个多小时 最后的成品就出了**  
>   
> **图如下**  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 6]

--------------------

> **对的 中间隔了一个分界线 就是希望如果你没有思路的话 看到上面的图 右边的 就应该明白怎么去完成这个Lab了 建议好好思考一下**  
>   
> **那我们这里就直接开始讲思路了  
> `Basic Version 1.0`的代码其实已经完成了相当大部分的任务了 我们最后只需要再加上一个双向链表即可 我的双向链表 大小类区分是以`2的幂`来进行区分的 通俗点就是`1-1` `2-3` `4-7` `8-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 但是感觉没有那么有兴趣 精品Lab且做且珍惜吧 那就先写到这啦 各位之后再见啦~**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 7]

--------------------

### 结束图 ###

--------------------

**放一张我特别喜欢的图吧 哈哈**

![在这里插入图片描述][6d28d9f8ad2b4c79be7a90a33e552caf.GIF]

[CSAPP Lab_ _ Lab]: https://love6.blog.csdn.net/article/details/120836083
[Computer Systems_ A Programmer_s Perspective_ 3_E _CS_APP3e]: http://csapp.cs.cmu.edu/3e/labs.html
[CSAPP 2010 labs cmu edu]: https://www.cs.cmu.edu/afs/cs/academic/class/15213-f10/www/labs/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/37fa0a1a88e140328050560461750cd6.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/cdeb39a4d3dc43bebf893be07282d119.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/e17dcd59e4764963964148972c959d2e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/83c50bc7cb0948ebafd8a4f3d4e18a33.png
[Love 6_s Private Blog CSDN_ Lab6 Malloc Lab _Traces]: https://download.csdn.net/download/qq_37500516/33986491
[Lab 6 Malloc Lab _ 12 traces Github]: https://github.com/Davon-Feng/CSAPP-Labs/tree/master/yzf-malloclab-handout/traces
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/8aac3f728a4b40c38c8a23e1d1094805.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/9d971e31b3f941cfa824371bf7c305f2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/4b24e5895e644faaa83f8e38e38ea94e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/cb6699791ae94c868b1a0fb1ae2ecb4b.png
[6d28d9f8ad2b4c79be7a90a33e552caf.GIF]: /images/20220828/7d964ce568f44718bf518bcb1fde39f2.png