首页 > 其他分享 >CSAPP Lab 7 Malloc Lab

CSAPP Lab 7 Malloc Lab

时间：2024-04-24 13:45:58浏览次数：33  
标签：CSAPP GET void LIST Malloc Lab bp PUT size

本次实验的内容也比较清晰，只需要完成一个手写的 malloc 动态内存分配器即可。

书上第 \(9\) 章第 \(9\) 节介绍了这样的分配器的实现方法。

实验要求

本次实验提供了基本的框架，需要完成下面几个函数：

int mm_init(void);
void *mm_malloc(size_t size);
void mm_free(void *ptr);
void *mm_realloc(void *ptr, size_t size);

分别是，分配器的初始化、分配内存、释放内存、重新分配内存等操作。

mdriver 程序将对分配器的空间利用率和吞吐量进行评判，如果 \(U\) 代表最终的空间利用率，\(T\) 代表吞吐量，那么我们的得分 \(P\) 就是它们的加权和：

\[P = wU + (1 -w)\min\left(1, \frac{T}{T_{libc}}\right) \]

其中，\(w\) 为加权系数，默认为 \(0.6\)。

组织结构和放置策略介绍

影响分配器的空间利用率和吞吐量最重要的因素就是空闲块的组织结构和放置策略。

具体地，一共有下面几种组织结构：

  • 隐式空闲链表（Implicit Free List）：把所有的块连接起来，而且是通过头部中的大小字段隐含地连接着的，每次都需要遍历所有块来找到合适的空闲块。
  • 显式空闲链表（Explicit Free Lists）：在空闲块中增加两个指针，分别指向链表中前一块和后一块，这样就不需要遍历所有块，只需要遍历空闲块。
  • 分离的空闲链表（Segregated Free Lists）：维护多个空闲链表，其中每个链表中的块有大致相等的大小。分为三种：
    • 简单分离存储（simple segregated storage）：每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类中最大元素的大小，从不合并与分离。
    • 分离适配（Segregated Fit）：分配器维护着一个空闲链表的数组。每个空闲链表是和一个大小类相关联的，并且被组织成某种类型的显式或隐式链表。每个链表包含潜在的大小不同的块， 这些块的大小是大小类的成员。
    • 伙件系统（buddy system）：分离适配的一种特例，其中每个大小类都是 \(2\) 的幂。

其中，C 标准库的 malloc 使用的就是分离适配的方法，在本实验中，为了对标 malloc，我们也将使用这种方法。

常见的放置策略有首次适配（first fit）、下一次适配（next fit）和最佳适配（best fit）：

  • 首次适配：从头开始搜素空闲链表，选择第 一个合适的空闲块。
  • 下一次适配：和首次适配很相似，只不过不是从链表的起始处开始每次搜索，而是从上一次查询结束的地方开始。
  • 最佳适配：检查每个空闲块，选择适合所需请求大小的最小空闲块。

一般来说，首次适配的优点是它趋向于将较大的空闲块保留在链表的后面，但是它趋向于在链表起始处留下小空闲块的 “碎片” ，这就增加了对较大块的搜索时间。最佳适配往往有用最好的空间利用率，但是需要完整遍历所有的空闲块。

在本实验中，我们将采用首次适配和最佳适配两种方式进行比较，选择最好的成绩。

事实上，即使使用首次适配，分离适配的空闲块组织结构已经带来了一部分最佳适配的特性。

宏定义

/* $begin mallocmacros */
/* Basic constants and macros */
#define WSIZE       4       /* Word and header/footer size (bytes) */ //line:vm:mm:beginconst
#define DSIZE       8       /* Double word size (bytes) */
#define CHUNKSIZE  (1<<12)  /* Extend heap by this amount (bytes) */  //line:vm:mm:endconst 

#define MAX(x, y) ((x) > (y)? (x) : (y))  

/* Pack a size and allocated bit into a word */
#define PACK(size, alloc)  ((size) | (alloc)) //line:vm:mm:pack

/* 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:getalloc

/* 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:prevblkp

/* 分离适配链表相关 */
#define LIST_PRE(bp) (bp)
#define LIST_NEXT(bp) ((void *)((char *)bp + WSIZE))
#define LIST_HEAD(x) ((void *)((char *)(heap) + WSIZE * (x)))
#define GET_PRE(bp) ((void *)GET(LIST_PRE(bp)))
#define GET_NEXT(bp) ((void *)GET(LIST_NEXT(bp)))
#define GET_HEAD(x) ((void *)GET((char *)(heap) + WSIZE * (x)))
/* $end mallocmacros */

大致和书上使用的宏定义相同，不过最后有几个和分离适配的链表相关，LIST_PRE 和 LIST_NEXT 表示这个块上存储上一块和下一块的位置的指针，LIST_HEAD 表示第 \(i\) 个大小类的头指针，GET_XXX 是这三个宏定义的解引用版本。

组织结构

./20230908-csapp-malloclab/image-20230908132615227

具体来说，分离适配的组织结构是上图的格式。

显然，因为头部和脚部，以及两个指针，一个空闲块至少有 \(4\) 个字。因此，我们一共分了 \(20\) 个大小类，第 \(0\) 个大小类的大小为 \(16\)，第 \(1\) 个大小类为 \(\{17, \dots, 32\}\)，以此类推，第 \(i(1 \leq i < 19)\) 个大小类为 \(\{2^{i+3} - 1, \dots, 2^{i+4} \}\)。最后一个大小类为剩下的所有大小。

因此，我们可以写出一个确定大小类编号的函数：

int getlist(size_t size) {
    for (int i = 0; i < 19; ++i)
        if (size <= (1 << (i + 4)))
            return i;
    return 19;
}

初始化

初始化首先要申请 \((20 + 4) \times 4\) 个字节的空间，作为头指针、填充块、序言块和结尾块的位置。

最后再调用 extend_heap 函数申请一个 \(2^{12}\) 大小的空闲块备用。

int mm_init(void)
{
    if ((heap = mem_sbrk(24 * WSIZE)) == (void*)-1) return -1;
    for (int i = 0; i < 20; ++i)
        PUT(LIST_HEAD(i), NULL);
    
    PUT(LIST_HEAD(20), 0);
    PUT(LIST_HEAD(21), PACK(DSIZE, 1));
    PUT(LIST_HEAD(22), PACK(DSIZE, 1));
    PUT(LIST_HEAD(23), PACK(0, 1));

    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) return -1;
    return 0;
}

extend_heap 的作用是将可用的堆空间扩展 CHUNKSIZE 个字节，这里是 \(2^{12}\)。

void *extend_heap(size_t size) {
    size = ((size % 2) ? size + 1 : size) * WSIZE;
    void *p = mem_sbrk(size);
    if (p == (void *)-1) return NULL;

    PUT(HDRP(p), PACK(size, 0));
    PUT(FTRP(p), PACK(size, 0));
    PUT(HDRP(NEXT_BLKP(p)), PACK(0, 1));
    
    return coalesce(p);
}

其中，coalesce 函数是用来合并空闲块的，将在稍后给出。

注意到堆的空间是连续的，因此申请得到的地址的前一个字节就是原来的结尾块，这里我们将它覆盖成新的空闲块，将申请到的空间的最后一块作为新的结尾块。

这里不需要将空闲块加入链表，会在 coalesce 中合并完空闲块再加入。

链表相关

插入

因为我们要实现首次适配和最优适配的两种模式，因此在插入链表的过程会有些差异。

下面是首次适配的版本，首先我们找到所属的大小类，如果头指针指向为空，就直接接在头指针下面，否则取代掉头指针指向块的位置，作为新的头指针指向。

void ins(void *bp) {
    size_t size = GET_SIZE(HDRP(bp));
    int list = getlist(size);
    if (GET_HEAD(list) == NULL) {
        PUT(LIST_NEXT(bp), NULL);
        PUT(LIST_HEAD(list), bp);
        PUT(LIST_PRE(bp), NULL);
    } else {
        PUT(LIST_PRE(GET_HEAD(list)), bp);
        PUT(LIST_NEXT(bp), GET_HEAD(list));
        PUT(LIST_HEAD(list), bp);
        PUT(LIST_PRE(bp), NULL);
    }
}

下面是最优适配的版本。这里，我们确保了每个大小块中，所有空闲块都是按照大小排序的，头指针指向的为最小的块，越向后大小越大。

因此，在插入的时候，我们要在链表中找到合适的位置才能插入。

void ins(void *bp) {
    size_t size = GET_SIZE(HDRP(bp));
    int list = getlist(size);
    if (GET_HEAD(list) == NULL) {
        PUT(LIST_NEXT(bp), NULL);
        PUT(LIST_HEAD(list), bp);
        PUT(LIST_PRE(bp), NULL);
    } else {
        void *p, *q;
        for (p = GET_HEAD(list), q = NULL; p; q = p, p = GET_NEXT(p))
            if (GET_SIZE(HDRP(p)) >= size) {
                if (q == NULL) PUT(LIST_HEAD(list), bp);
                else PUT(LIST_NEXT(q), bp);
                PUT(LIST_NEXT(bp), p);
                PUT(LIST_PRE(p), bp);
                PUT(LIST_PRE(bp), q);
                return;
            }
        if (q == NULL) PUT(LIST_HEAD(list), bp);
        else PUT(LIST_NEXT(q), bp);
        PUT(LIST_NEXT(bp), p);
        if (p) PUT(LIST_PRE(p), bp);
        PUT(LIST_PRE(bp), q);
    }
}

删除

删除部分就简单了，不需要区分是哪种适配，只需要修改原本的前驱、后继的相关指针即可。

void del(void *bp) {
    size_t size = GET_SIZE(HDRP(bp));
    int list = getlist(size);
    if (GET_PRE(bp) == NULL) PUT(LIST_HEAD(list), GET_NEXT(bp));
    else PUT(LIST_NEXT(GET_PRE(bp)), GET_NEXT(bp));
    if (GET_NEXT(bp)) PUT(LIST_PRE(GET_NEXT(bp)), GET_PRE(bp));
}

合并与切割

合并

合并的过程是将连续的空闲块合成一个。因为我们采用了立即合并的思路，只要有新的空闲块诞生就立刻合并，保证了任意时刻空闲块都是不连续的。

具体的方法是判断新的空闲块的前一个块和后一个块是不是空闲的，将相邻的空闲块在原来的链表中删除，合并在一起，插入新的链表。

void *coalesce(void *bp) {
    int prea = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    int nexta = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));
    
    if (prea && nexta) ;
    else if (prea && !nexta) {
        del(NEXT_BLKP(bp));
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    } else if (!prea && nexta) {
        del(PREV_BLKP(bp));
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        bp = PREV_BLKP(bp);
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    } else if (!prea && !nexta) {
        del(NEXT_BLKP(bp));
        del(PREV_BLKP(bp));
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(HDRP(NEXT_BLKP(bp)));
        bp = PREV_BLKP(bp);
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }
    ins(bp);
    return bp;
}

切割

分离就是在需要使用空闲块的时候，将一个空闲块切割成需要的已分配块，和新的空闲块。

因为空闲块的大小至少为 \(4\)，因此如果空闲块大小和需要分配的大小之差小于 \(4\)，我们直接将整个空闲块分配掉，否则需要切割出来。

void place(void *bp, size_t size) {
    size_t bsize = GET_SIZE(HDRP(bp));
    del(bp);
    if (bsize - size >= 4 * WSIZE) {
        PUT(HDRP(bp), PACK(size, 1));
        PUT(FTRP(bp), PACK(size, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(bsize - size, 0));
        PUT(FTRP(bp), PACK(bsize - size, 0));
        ins(bp);
    } else {
        PUT(HDRP(bp), PACK(bsize, 1));
        PUT(FTRP(bp), PACK(bsize, 1));
    }
}

寻找空闲块

寻找空闲块的思路很简单，找到的大小所在的大小类，先搜索这个大小类中是否有合适的块，如果找到就可以返回了。如果没有找到，就向大一级的大小类中继续找，直到找到为止。

这里就是分离适配的组织结构最大的优势了。既避免了在搜索特别小的大小类中浪费时间，也尽可能保证了搜索得到的块是比较小的。

void *find_fit(size_t size) {
    for (int list = getlist(size);  list < 20; ++list)
        for (void *bp = GET_HEAD(list); bp; bp = GET_NEXT(bp))
            if (GET_SIZE(HDRP(bp)) >= size)
                return bp;
    return NULL;
}

mm_malloc，mm_free 和 mm_realloc

下面就是本次实验的主角了。

mm_malloc

mm_malloc 的思路很简单，首先将需要分配的大小调整到合适的。这里需要调整的有加上头部和脚部的大小，还有双字对齐，还有如果需要分配的大小小于 \(4\) 个字。，那么就将大小改成 \(4\) 个字。

然后，使用 find_fit 函数找到合适的空闲块。如果找到就可以调用 place 来分割放置了。如果找不到，就要调用 extend_heap 来扩大堆空间，寻找新的空闲块。

void *mm_malloc(size_t size)
{
    if (size == 0) return NULL;
    if (size <= DSIZE) size = 2 * DSIZE;
    else size = size + DSIZE;
    size = (size + DSIZE - 1) / DSIZE * DSIZE;

    void *bp = find_fit(size);
    if (bp != NULL) {
        place(bp, size);
        return bp;
    }

    if ((bp = extend_heap(MAX(size, CHUNKSIZE) / WSIZE)) == NULL) return NULL;
    place(bp, size);
    return bp;
}

mm_free

mm_free 函数比较简单，将这个块的头部、脚部标记为空闲块，调用 coalesce 合并空闲块并插入链表即可。

void mm_free(void *ptr)
{
    if (ptr == NULL) return;
    size_t size = GET_SIZE(HDRP(ptr));
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    coalesce(ptr);
}

mm_realloc

mm_realloc 函数实验提供的程序中已经完成了，除了查询 size 的一个小问题以外可以直接使用。

大致的思路就是先调用 mm_malloc 分配更大的空间，然后使用 memcpy 将内容复制过去，最后使用 mm_free 释放旧的空间。

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;
    copySize = GET_SIZE(HDRP(ptr));
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

测试和评分

首次适配版本：

./20230908-csapp-malloclab/image-20230908135539982

最优适配版本：

./20230908-csapp-malloclab/image-20230908135557406

可以发现，两种方法的差距其实并不是很大，这可以说明分离适配的策略其实已经足以使得首次适配的空间表现接近最优适配了，也足以让最优适配的时间消耗大大降低。

程序

点击这个 链接 查看程序！

标签：CSAPP,GET,void,LIST,Malloc,Lab,bp,PUT,size
From： https://www.cnblogs.com/hankeke303/p/18155103/csapp-malloclab

相关文章

  • CSAPP Lab 8 Proxy lab
    终于到最后一个Lab啦！这个Lab的任务是实现一个代理服务器，将客户端发送的请求转发到服务端。这个Lab分为三个任务，第一个任务需要实现这个代理服务，第二个任务支持处理并发请求，第三个任务需要实现缓存。PartI:Implementingasequentialwebproxy这个部分其实很好写，很多......
  • CSAPP Lab-1 DATALAB
    本文原发于2023-09-0215:32:57于我的hexo博客，现迁移至此。最近看完了CSAPP整本书，发现官网上还有11次实验可以做。UPD：好像只有9个，因为有两个是旧版本的，可以被新版的替代掉。UPD：好像只有8个，performance也算是旧的实验了，但是没有明确指出。Lab地址：http://csapp.cs......
  • CSAPP Lab-3 ATTACKLAB
    书接上回，这次做到了第三个Lab啦。任务描述这一个Lab的任务就更有意思了，实验给了我们两个程序，每个程序都会让我们输入一行字符串，而它们是通过下面这个函数来读取的：unsignedgetbuf(){ charbuf[BUFFER_SIZE]; Gets(buf); return1;}其中，Gets函数和C库的gets函数......
  • CSAPP Lab-4 Architecture Lab
    本次实验是有关书上第四章设计的Y86-64处理器的，实验分为三个部分，分别是编写几个简单的Y86-64程序、使用一条新指令扩展SEQ模拟器以及优化Y86-64的基准测试程序和处理器设计。实验准备需要简单复习一下Y86-64的指令集架构以及处理器架构呢。指令集架构指令集：指令功......
  • CSAPP Lab5 Cache Lab
    到实验5啦！这次的实验是有关高速缓存的。让我们先来复习一下高速缓存的基础知识吧！复习高速缓存的结构在一个存储器地址有\(m\)位的系统上，一共有\(M=2^m\)个地址。假设高速缓存被组织成一个有\(S=2^s\)个高速缓存组的数组，其中每个组包括\(E\)个高速缓存行，每行存......
  • CSAPP Lab6 Shell Lab
    本次实验的任务很清晰，实现一个简单的UnixShell。需要用到基础的进程控制、信号处理等知识。简单来说，实验已经提供了一些简单的功能，我们需要在此基础上，实现下面的功能：eval：解析和解释命令行的主例程。[70行]builtin_cmd：识别并解释内置命令quit（退出）、fg（前台运行某个作业）、bg（后......
  • CSAPP Lab-2 BOMBLAB
    第二个Lab就比较有趣了。这一个Lab的任务是，我们得到了一个bomb炸弹程序，这个炸弹程序有\(6\)个phase，每个phase都会读取我们的输入，判断我们的输入是否符合要求，如果正确这个phase的炸弹就会被拆除，否则炸弹就会爆炸。我们需要借助各种工具，对程序进行反汇编等等，获得能够......
  • 伯克利大学 CS61B Lab配置教程
    基本过程：首先将伯克利大学的代码框架下载到自己的电脑，然后我们直接在框架里修改就行将自己的代码上传到github上，然后使用伯克利大学的Gradescope评测自己写的代码下载代码在自己电脑桌面新建一个文件夹，这里我命名为：cs61b，打开gitbash，使用cd进入我们新创建的文件夹，注意路径......
  • 读《我和Labview》5条件结构和顺序结构
    5条件结构和顺序结构条件结构布尔类型条件选择结构其它数据类型的条件选择是否要设置默认分支？合理设置悬着条件隧道避免把控件放在条件结构内选择函数顺序结构程序执行顺序创建顺序结构层叠式顺序结构平铺式顺序结构无形胜有形的最高境界6用户自定义控件7控件的局......
  • pwn知识——劫持__malloc_hook（在加入tcache以后）
    导论动调是最好的导师！malloc_hook函数解析malloc_hook是malloc的钩子函数，在执行malloc时，会先检测__malloc_hook的值，如果malloc_hook的值存在，则执行该地址（值里边表现为十六进制，可以成为地址），也就是说，如果我们成功劫持malloc_hook以后并修改它的值为one_gadget，我们就能getshell并......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99