CSAPP LAB-5 手写动态存储分配器

我也大概察觉到我们课程的实验是挑着 CSAPP 中原版实验去做的，并进行了简化，所以和网上的实验顺序不太一样，但内容是大致相同的。

CSAPP LAB 实验

• CSAPP LAB-1 位操作
• CSAPP LAB-2 二进制炸弹实验
• CSAPP LAB-3 缓冲区溢出炸弹
• CSAPP LAB-4 代码优化
• CSAPP LAB-5 手写动态存储分配器（本文）

这次的实验建议先看课本的第九章的 9.9 部分（《CSAPP》第三版），理解其中的内容后进行实现。而且大部分代码课本上都有。不管你现在《CSAPP》学到哪一个部分，都可以直接看 9.9 章，不用担心没有铺垫内容。

本文将介绍一个动态存储分配器的简单实现：隐式空闲链表 + 立即边界标记合并方式 + 首次匹配/下次匹配算法。更高级的实现可以看文末参考文章。

这是我 CSAPP 课程的最后一个实验了，每次专挑👩助教验收，温柔贴心给分高😍！

实验介绍和要求

本实验需要用 c 语言实现一个动态的存储分配器，也就是你自己版本的 malloc，free，realloc 函数。

解压文件：

tar xvf malloclab-handout.tar

我们需要修改的唯一文件是 mm.c，包含如下几个需要实现的函数：

/*
mm_init:在调用mm_malloc，mm_realloc或mm_free之前，调用mm_init进行初始化，正确返回0。
*/
int mm_init(void); 

/*
mm_malloc：在堆区域分配指定大小的块，分配的空间，返回的指针应该是8字节对齐的
*/
void *mm_malloc(size_t size); 

/*
mm_free:释放指针指向的block
*/
void mm_free(void *ptr); 

/*
返回指向一个大小为size的区域指针，满足一下条件：
* if ptr is NULL, the call is equivalent to mm_malloc(size); 
* if size is equal to zero, the call is equivalent to mm_free(ptr); 
* if ptr is not NULL：先按照size指定的大小分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来ptr所指内存区域
*/
void *mm_realloc(void *ptr, size_t size);

记住哦，本次实验的任务要求之一是指针是 8 字节对齐的。

我们可以调用实验提供给我们的函数，这些函数定义在 memory.c 中：

• void *mem_sbrk(int incr): Expands the heap by incr bytes, where incr is a positive non-zero integer and returns a generic pointer to the first byte of the newly allocated heap area.
• void *mem_heap_lo(void): Returns a generic pointer to the first byte in the heap.
• void *mem_heap_hi(void): Returns a generic pointer to the last byte in the heap.
• size_t mem_heapsize(void): Returns the current size of the heap in bytes.
• size_t mem_pagesize(void): Returns the system’s page size in bytes (4K onLinux systems).

在这篇文章的实现方式中，只需要使用 void *mem_sbrk(int incr)，与标准实现不同的是，这个函数拒绝收缩堆的请求，也就是不能输入负数。mem_sbrk 的作用可以结合课本 9.9 章进行理解。

验证我们的动态的存储分配器：

• mdriver.c：负责测试 mm.c 的正确性,空间利用率和吞吐量
• 执行 make 指令生成 mdriver 可执行文件
• mdriver 的使用：
  • -f <tracefile>: -f 后添加一些 trace file 来测试我们实现的函数
  • -V: 打印出诊断信息。
  • 例如：./mdriver -V -f short1-bal.rep

一些编程规则：

• 不能改变 mm.c 中函数接口
• 不能直接调用任何内存管理的库函数和系统函数 malloc, calloc, free, realloc, sbrk, brk
• 不能定义任何全局或者静态复合数据结构如 arrays, structs, trees，允许使用 integers, floats 以及 pointers 等简单数据类型
• 返回的指针需要 8 字节对齐

关键概念

我把课本涉及到的关键概念模型简要介绍一下。

本文介绍的是隐式空闲链表 + 立即边界标记合并方式 + 首次匹配/下次匹配算法。

更多详细内容理解就看下一节的代码注释咯！

隐式空闲链表的恒定形式

一个正方形表示 4 字节（一个字），虚线表示双字对齐标志。正方形中的头部尾部标记为 size/is_alloc。

标记边界合并

Knuth 提出了边界标记技术，允许在常数时间内进行对前面的块的合并。

这种思想，是在每个块的结尾处添加一个脚部（footer，边界标记），其中脚部就是头部的一个副本。如果每个块包括这样一个脚部，那么分配器就可以通过检查它的脚部，判断前面一个块的起始位置和状态，这个脚部总是在距当前块开始位置一个字的距离。

考虑当分配器释放当前块时所有可能存在的情况：

1. 前面的块和后面的块都是已分配的。
2. 前面的块是已分配的，后面的块是空闲的。
3. 前面的块是空闲的，而后面的块是已分配的。
4. 前面的和后面的块都是空闲的。

匹配算法

匹配算法：

• 首次匹配（First Fit）。从头开始搜索空闲链表，选择第一个合适的空闲块。
  • 优点：趋向于将大的空闲块保留在链表的后面。
  • 缺点：它趋向于在靠近链表起始处留下小空闲块的「碎片」，增大了对较大块的搜索时间。
• 下一次适配（Next Fit）。和首次适配很相似，只不过不是从链表的起始处开始每次搜索，而是从上一次查询结束的地方开始。由 Donald Knuth 提出。基于思想：如果上一次在某个空闲块里发现了一个匹配，那么很可能下一次我们也能在这个剩余块中发现匹配。
  • 优点：比首次适配运行起来明显快一些。
  • 缺点：内存利用率比首次匹配低。
• 最佳适配（Best Fit）。最佳适配检查每个空闲块，选择适合所需请求大小的最小空闲块。
  • 优点：内存利用率较高。
  • 缺点：在简单空闲链表组织结构中（比如上面提到的隐式空闲链表），需要对堆进行彻底搜索。

mm.c 文件

/*
 * mm-naive.c - The fastest, least memory-efficient malloc package.
 *
 * In this naive approach, a block is allocated by simply incrementing
 * the brk pointer.  A block is pure payload. There are no headers or
 * footers.  Blocks are never coalesced or reused. Realloc is
 * implemented directly using mm_malloc and mm_free.
 *
 * NOTE TO STUDENTS: Replace this header comment with your own header
 * comment that gives a high level description of your solution.
 */
#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 */
    "SA23xxxxxx",
    /* First member's full name */
    "uuanqin",
    /* First member's email address */
    "[email protected]",
    /* Second member's full name (leave blank if none) */
    "",
    /* Second member's email address (leave blank if none) */
    ""};

/*********  一些必要的宏 ***************/

/* 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)  // 每次扩展堆时使用这个大小


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

#define PACK(size, is_alloc) ((size) | (is_alloc))   // 将大小和分配位打包组装

// 读取/写入 指定位置的值
#define GET(p) (*(unsigned int *)(p))                
#define PUT(p, val) (*(unsigned int *)(p) = (val))

// 获取头部的信息
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

// 给定块的指针bp，获取其头部和脚部的指针（注意，bp指向有效载荷的第一个字节）
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) // 依赖与头部已分配好大小

// 给定块的指针bp，计算前后块的指针（注意，bp指向有效载荷的第一个字节）
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

// 堆的起始位置
static void *heap_listp; // 总是指向序言块，我们可以小小优化为指向下一个块

// 函数注册
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void *find_fit(size_t asize);
static void place(void *bp,size_t asize);

// 是否启动下次适配
#define NEXT_FIT

static void *algo_first_fit(size_t asize);

#ifdef NEXT_FIT
    static void *algo_next_fit(size_t asize);
#endif


/*
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    // 创建一个空的空闲链表
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
    {
        return -1;
    }
    // 因为序言块+结尾块只需要三个字节。我们又必须保证堆的开始位置是双字对齐的。
    // PUT(heap_listp, 0);  // 课本中加了这一条，主要是为了占位，没有什么含义。
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // 序言块头部
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // 序言块脚部
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1));     // 结尾块头部
    heap_listp += (2 * WSIZE);                     // 移动堆指针到序言块中间

    // 使用空闲块扩展堆
    if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
    {
        return -1;
    }

    return 0;
}

static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; // 保证size是奇数个字节，因为有一个字节用来放空闲块的头部
    if ((long)(bp = mem_sbrk(size)) == -1)
    {
        return NULL;
    }
    PUT(HDRP(bp), PACK(size, 0));           // 空闲块的头部
    PUT(FTRP(bp), PACK(size, 0));           // 空闲块的尾部
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));  // 新的结尾块

    return coalesce(bp); // 合并块
}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *ptr)
{
    size_t size = GET_SIZE(HDRP(ptr));
    // 对当前块的标记位进行改变
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));
    coalesce(ptr);
}

// 合并块
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;
}



/*
 * 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)
{
    size_t asize; // 预留了头部和脚部的大小
    size_t extend_size;
    char *bp;
    if (size <= 0)
        return NULL;

    // 由于边界双字对齐的情况，最小的分配大小是DSIZE。头部4+尾部4+最小的内容为1->对齐边界后为16（CSAPP 课本练习题9.7）
    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        // 需要分配的大小+头部+尾部
        asize = ALIGN(size+DSIZE); // ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
        // 课本：asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE); 

    // 使用适配算法
    if ((bp = find_fit(asize)) != NULL)
    {
        place(bp, asize);
        return bp;
    }

    // 找不到合适的匹配就扩展
    extend_size = MAX(asize, CHUNKSIZE);
    if ((bp = extend_heap(extend_size / WSIZE)) == NULL)
    {
        return NULL;
    }
    place(bp, asize);
    return bp;
}



/*
 * mm_realloc - Implemented simply in terms of mm_malloc and 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;
    if (ptr == NULL)
    {
        return newptr;
    }

    copySize = GET_SIZE(HDRP(oldptr));
    if (size < copySize)
        copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
    // return NULL;
}

// 放置块（课本练习9.9）
static void place(void *bp,size_t asize){
    size_t free_block_size = GET_SIZE(HDRP(bp));

    // 空闲块减去需要分配的大小，得到的碎片必须至少能容纳一个最小的可分配的块（2*DSIZE，也就是头部4+尾部4+最小的内容为1->对齐边界后为16）
    if((free_block_size - asize)>=2*DSIZE){
        // 裁剪
        PUT(HDRP(bp),PACK(asize,1));
        PUT(FTRP(bp),PACK(asize,1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp),PACK(free_block_size-asize,0));
        PUT(FTRP(bp),PACK(free_block_size-asize,0));
    }else{
        PUT(HDRP(bp),PACK(free_block_size,1));
        PUT(FTRP(bp),PACK(free_block_size,1));
    }

}

/***** 适配算法  ******/

static void *find_fit(size_t asize){
    // asize 预留了头部和脚部的大小
#ifdef NEXT_FIT
    return algo_next_fit(asize);
#else
    return algo_first_fit(asize);
#endif
}

// 首次匹配算法（课本练习9.8）
static void *algo_first_fit(size_t asize){
    void* bp =heap_listp;
    while(GET_SIZE(HDRP(bp))>0){
        if(!GET_ALLOC(HDRP(bp)) && (asize<=GET_SIZE(HDRP(bp)))){
            return bp;
        }
        bp = NEXT_BLKP(bp);
    }
    return NULL;
}

// 下次适配算法
#ifdef NEXT_FIT
    static void* last_heap_listp = NULL; // 上次遍历的指针
    static void *algo_next_fit(size_t asize){
        void* bp;
        if(last_heap_listp!=NULL){
            bp =last_heap_listp;
        }else{
            bp =heap_listp;
        }
        
        while(GET_SIZE(HDRP(bp))>0){
            if(!GET_ALLOC(HDRP(bp)) && (asize<=GET_SIZE(HDRP(bp)))){
                last_heap_listp=bp;
                return bp;
            }
            bp = NEXT_BLKP(bp);
        }
        last_heap_listp = NULL;

        // 从头再搜索一遍
        return algo_first_fit(asize);
    }
#endif

后记

这个实验，手打代码，bug 真多。真不能相信肉眼对照，只能信 CV 大法。

限于教学安排和本人时间，CSAPP LABS 就更新到这里。其实这些实验要基本完成也并不困难，在操作的同时可以学到许多 C 语言的知识，积累编程经验，对后续理解计算机都有帮助。

希望大家在知识的海洋里、在存储器山中收获满满！🥳🥳🥳

本文参考

• 《CSAPP》第三版第九章内容
• CSAPP课程Lab6 Malloc Lab - 知乎 (zhihu.com)
• CSAPP之详解MollocLab - 简书 (jianshu.com)