malloc_lab

实验目的

1. 这是一个实现动态内存分配器的实现，类似实现C语言标准库中的malloc free realloc 函数
2. mm_init(void)
   1. 初始化堆内存区域
   2. 为后续的内存分配操作做准备
   3. 成功返回0，失败返回-1
3. mm_malloc(size_t size)
   1. 分配至少size字节的内存
   2. 返回的指针必须8字节对齐
   3. 不能与其他已分配的内存重叠
4. *mm_free(void ptr)
   1. 释放之前分配的内存块
   2. 只能释放由 mm_malloc 或 mm_realloc 分配且尚未释放的块
5. *mm_realloc(void ptr, size_t size)
   1. 重新调整已分配内存块的大小
   2. 特殊情况处理
      1. ptr == NULL → 相当于 mm_malloc(size)
      2. size == 0 → 相当于 mm_free(ptr)

代码实现

/*
 * 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 */
    "TJU",
    /* First member's full name */
    "Student",
    /* First member's email address */
    "student@tju.edu.cn",
    /* 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              // 字和头部/脚部的大小（bytes)
#define DSIZE 8              // 双字
#define CHUNKSIZE (1 << 12)  // 按照CHUNKSIZE大小（bytes)扩展堆

#define MAX(x, y) ((x) > (y) ? (x) : (y))
//将大小和已分配位结合起来并返回一个值，可以把它存放在头部或者脚部中
#define PACK(size, alloc) ((size) | (alloc))
//读取和返回参数P引用的字。
#define GET(p) (*(unsigned int *)(p))
//将val存放在参数p指向的字中
#define PUT(p, val) (*(unsigned int *)(p) = (val))
//从地址 P处的头部或者脚部返回块大小
#define GET_SIZE(p) (GET(p) & ~0x7)
//从地址 P处的头部或者脚部返回已分配位
#define GET_ALLOC(p) (GET(p) & 0x1)
//返回指向这个块的头部指针
#define HDRP(bp) ((char *)(bp)-WSIZE)
//返回指向这个块的脚部指针
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
//分别返回指向后面的块和前面的块的块指针。
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE)))

//bp块的next指针
#define NEXT_LINK_RP(bp) ((char *)(bp))
//bp块的prev指针
#define PREV_LINK_RP(bp) ((char *)(bp) + WSIZE)



/* 全局变量 */

//堆头
static char* heap_listp;
//空闲链表数组头
static char* block_list_start;


//共11个大小类，最后一个大小类表示大于8192的所有块，剩下的大小类表示区间
#define SIZE_0 16  //空闲块的设计以及对齐要求，最小的块要求为16字节，所以从2^4次方开始
#define SIZE_1 32  //<=32
#define SIZE_2 64  //<=64
#define SIZE_3 128 //...
#define SIZE_4 256
#define SIZE_5 512
#define SIZE_6 1024
#define SIZE_7 2048
#define SIZE_8 4096
#define SIZE_9 8192
// 大小类的块大小划分最多到2^13=8192，因为测试文件测试的大小大多不超过8192
#define SIZE_SET_NUM 11


/*定义的辅助函数 */
static void* extend_heap(size_t words);//扩展堆，扩展words个字(4 byte)
static void* place(void* bp, size_t asize);//分配bp指向的块，asize个字节
static void* find_fit(size_t asize);//查找空闲块
static void* coalesce(void* bp);//合并空闲块
static char* find_list(size_t size);//查找size对应的空闲链表类
static void _insert(char* bp);//插入空闲链表
static void _remove(char* bp);//从空闲链表移除

static void printblock(void* bp);//打印块信息
static int checkheap(int verbose);//检查堆
static int checkblock(void* bp);//检查单个块
static void printlist(void* bp, int size);//打印一个空闲链表
static int checklist(void* bp, int size);//检查一个空闲链表


//初始化堆
int mm_init(void) {
    //需要额外的14个初始字
    if ((heap_listp = mem_sbrk(14 * WSIZE)) == (void*)-1)
        return -1;
    int i = 0;
    for (i = 0; i < 11; ++i) {//初始化前10个块，用于空闲链表数组表示
        PUT(heap_listp + (i * WSIZE), 0);
    }
    PUT(heap_listp + (11 * WSIZE), PACK(DSIZE, 1));  // 序言头，大小为8，已分配
    PUT(heap_listp + (12 * WSIZE), PACK(DSIZE, 1));  // 序言尾
    PUT(heap_listp + (13 * WSIZE), PACK(0, 1));      // 结尾块，大小为0，已分配
    //更新空闲链表数组起始地址
    block_list_start = heap_listp;
    //堆空间起始地址
    heap_listp += (12 * WSIZE);
    //扩展堆空间
    if (extend_heap((CHUNKSIZE + 24) / WSIZE) == NULL)
        return -1;
    return 0;
}


/*
 * mm_malloc - 分配至少size个字节的块
 */
void* mm_malloc(size_t size) {
    size_t asize;       // 调整后的块的大小
    size_t extendsize;  // 堆需要扩展的大小
    char* bp;
    //如果没有初始化，则初始化
    if (heap_listp == 0) {
        mm_init();
    }
    if (size == 0)
        return NULL;
    // 调整块大小，包括头部和脚部的开销以及对齐要求
    //至少16字节
    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else  // 加上开销字节，向上取整到8的倍数
        asize = DSIZE * ((size + (DSIZE)+(DSIZE - 1)) / DSIZE);

    // 如果找到了合适的空闲块，直接分配
    if ((bp = find_fit(asize)) != NULL) {
        return place(bp, asize);	//分割空闲块
    }

    // 如果没找到，扩展堆，再分配
    extendsize = MAX(asize, CHUNKSIZE);

    if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
        return NULL;
    return place(bp, asize);
}

/*
 * mm_free - 释放块
 */
void mm_free(void* bp) {

    if (bp == 0)
        return;

    if (heap_listp == 0) {
        mm_init();
    }
    //获取要释放的块大小
    size_t size = GET_SIZE(HDRP(bp));
    //释放，调整分配位即可
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    //合并
    coalesce(bp);
}



/*
 * mm_realloc - realloc实现
 */
void* mm_realloc(void* ptr, size_t size) {
    void* newptr = ptr;
    size_t copySize, asize, total_size;

    // size==0,只需要进行释放
    if (size == 0) {
        mm_free(ptr);
        return NULL;
    }
    // 如果ptr为空，只需要调用mm_malloc即可
    if (ptr == NULL) {
        return mm_malloc(size);
    }
    //调整块大小
    if (size <= DSIZE)
        asize = 2 * DSIZE;
    else
        asize = DSIZE * ((size + (DSIZE)+(DSIZE + 1)) / DSIZE);
    ssize_t old_size = GET_SIZE(HDRP(ptr));
    ssize_t next_size = GET_SIZE(HDRP(NEXT_BLKP(ptr)));
    ssize_t prev_size = GET_SIZE(HDRP(PREV_BLKP(ptr)));
    // 原先size大小满足要求，直接返回原指针
    if (old_size >= asize)
        return ptr;
    //后面的块为空闲状态，且与后面的块合并可以满足要求
    else if (!GET_ALLOC(HDRP(NEXT_BLKP(ptr))) && old_size + next_size >= asize) {
        //新块大小为当前块加上后面块
        total_size = old_size + next_size;
        //移除后面块结点
        _remove(NEXT_BLKP(ptr));
        //设置头脚块
        PUT(HDRP(ptr), PACK(total_size, 1));
        PUT(FTRP(ptr), PACK(total_size, 1));
    }
    //此块为堆中最后面的块，则直接扩展堆
    else if (!next_size) {
        if (extend_heap(MAX(asize - old_size, CHUNKSIZE)) == NULL) 
            return NULL;
        //新块大小为当前块加上扩充的大小
        total_size = old_size + GET_SIZE(HDRP(NEXT_BLKP(ptr)));
        //移除后面块结点
        _remove(NEXT_BLKP(ptr));
        //设置头脚块
        PUT(HDRP(ptr), PACK(total_size, 1));
        PUT(FTRP(ptr), PACK(total_size, 1));
    }
    //前面的块为空闲，且前面加当前块大小满足要求
    else if (!GET_ALLOC(HDRP(PREV_BLKP(ptr))) && old_size + prev_size >= asize) {
        //新块大小为前面块加上当前块
        total_size = old_size + prev_size;
        //移除前面块的结点
        _remove(PREV_BLKP(ptr));
        //设置头脚块
        PUT(FTRP(ptr), PACK(total_size, 1));
        PUT(HDRP(PREV_BLKP(ptr)), PACK(total_size, 1));
        newptr = PREV_BLKP(ptr);
        //复制数据
        memmove(newptr, ptr, old_size);  // 有可能出现重叠区域要用memmove来代替memcpy
    }
    else {
        //不是以上情况，则重新分配块，并复制数据
        newptr = mm_malloc(asize);
        memcpy(newptr, ptr, old_size - DSIZE);  //-DSIZE 是减去头部脚部的开销
        mm_free(ptr);
    }

    return newptr;
}
/*
 * mm_check - 检查堆的正确性
 */
//堆一致性检查
int mm_check(void) {
    //检查整个堆
    return checkheap(0);
    //checkheap(1);打印额外调试信息
}


/*  *   *   *   *   *   *   *   *   *   *   *   *   *   *   */
/*  *   *   *   *   *   辅助程序函数  *   *   *   *   *   */
/*  *   *   *   *   *   *   *   *   *   *   *   *   *   *   */


/*
 * coalesce - 边界标签合并。返回合并后数据块的指针
 */
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) {            // case 1，下一个块为空闲
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));  // 加上下一个块的size
        _remove(NEXT_BLKP(bp));                 // 从空闲链表删除下一个块
        PUT(HDRP(bp), PACK(size, 0));           // 修改bp块的头部
        PUT(FTRP(bp), PACK(size, 0));           // 修改“下一块”的脚部，
        //因为FTRP通过HDRP起作用，所以直接调用bp即可
    }
    else if (!prev_alloc && next_alloc) {  // case 2上一个块为空闲
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        _remove(PREV_BLKP(bp));
        PUT(FTRP(bp), PACK(size, 0));//修改bp的脚部
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));//通过PREV_BLKP(bp)而不是直接bp
        bp = PREV_BLKP(bp);
    }
    else if (!prev_alloc && !next_alloc) {  // case 3上下两个块皆为空闲
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        _remove(PREV_BLKP(bp));
        _remove(NEXT_BLKP(bp));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }
    _insert(bp);  // 插入合并后的块

    return bp;
}

 /*
  * extend_heap -扩展堆顶指针，共words * 4个字节，并考虑对齐
  */
static void* extend_heap(size_t words)
{
    char* bp;
    size_t size;

    /* 确定分配的字节数 */
    //分配偶数个字
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; 
    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);                                         
}

/*
 * place - 将大小为asize字节的数据块放置在空闲块bp的开始位置，
 *         如果剩余部分至少达到最小块大小，则进行分割
 */
static void* place(void* bp, size_t asize) {
    void* res_bp = bp;
    //原先的大小
    size_t csize = GET_SIZE(HDRP(bp));
    //剩余大小
    size_t remain_size = csize - asize;
    _remove(bp);  // 先从空闲链表删除bp块
    //剩余的不足以建立新的块，当作内碎片
    if (remain_size < (2 * DSIZE)) {
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
    //如果需要分配的块大小小于80，则把分割剩下的空闲块放在前面，分配块放在后面
    else if (asize < 88) {
        PUT(HDRP(bp), PACK(remain_size, 0));
        PUT(FTRP(bp), PACK(remain_size, 0));
        _insert(bp);
        bp = NEXT_BLKP(bp);
        res_bp = bp;
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
    }
    //如果需要分配的块大小大于80，则分配块在前面。
    else {
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));  // 需要注意的是：FTRP是通过HDRP运作的，所有要注意两者的先后关系
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(remain_size, 0));
        PUT(FTRP(bp), PACK(remain_size, 0));
        _insert(bp);
    }
    return res_bp;
}
/*
 * find_fit - 查找空闲块,使用首次适配（有序空闲链表的首次适配相当于最佳适配）
 */
static void* find_fit(size_t asize) {
    // 从适当的空闲链表头开始查找
    char* head = find_list(asize);
    // 如果在head的空闲链表找不到，就搜索下一个更大的大小类的空闲链表
    for (; head < block_list_start + (SIZE_SET_NUM * WSIZE); head += WSIZE) {
        char* bp = GET(head);
        // 遍历当前链表中的所有空闲块
        while (bp) {
            if (GET_SIZE(HDRP(bp)) >= asize)
                return bp;
            bp = GET(NEXT_LINK_RP(bp));
        }
    }
    // 如果没找到，返回NUL
    return NULL;
}

//查找对应类的空闲链表
static char* find_list(size_t size) {
    int i = 0;
    if (size <= SIZE_0)
        i = 0;
    else if (size <= SIZE_1)
        i = 1;
    else if (size <= SIZE_2)
        i = 2;
    else if (size <= SIZE_3)
        i = 3;
    else if (size <= SIZE_4)
        i = 4;
    else if (size <= SIZE_5)
        i = 5;
    else if (size <= SIZE_6)
        i = 6;
    else if (size <= SIZE_7)
        i = 7;
    else if (size <= SIZE_8)
        i = 8;
    else if (size <= SIZE_9)
        i = 9;
    else
        i = 10;

    return block_list_start + (i * WSIZE);
}

// 链表移除节点
static void _remove(char* bp) {
    char* head_ptr = find_list(GET_SIZE(HDRP(bp)));  // 地址
    char* head = GET(head_ptr);                      // 值
    char* next = GET(NEXT_LINK_RP(bp));
    char* prev = GET(PREV_LINK_RP(bp));

    if (prev == head_ptr) {  //bp是头节点后面第一个结点
        if (next) {//bp后面有结点
            PUT(PREV_LINK_RP(next), prev);
            PUT(head_ptr, next);
        }
        else {//bp是（链表中）最后一个结点
            PUT(head_ptr, NULL);
        }
    }
    else {  // bp不是头节点后面第一个
        if (next) {//bp后面有结点
            PUT(PREV_LINK_RP(next), prev);
            PUT(NEXT_LINK_RP(prev), next);
        }
        else {//bp是最后一个
            PUT(NEXT_LINK_RP(prev), NULL);
        }
    }
}

//插入对应的空闲链表
static void _insert(char* bp) {
    // 指针先初始化为空
    PUT(NEXT_LINK_RP(bp), 0);
    PUT(PREV_LINK_RP(bp), 0);

    int bp_size = GET_SIZE(HDRP(bp));
    //寻找对应空闲链表
    char* head_ptr = find_list(bp_size);
    //当前空闲块的结点
    char* cur = GET(head_ptr);
    // 如果链表为空（即头节点为空），则新内存块成为链表的头节点
    if (!cur) {
        PUT(NEXT_LINK_RP(bp), cur);
        PUT(PREV_LINK_RP(bp), head_ptr);
        PUT(head_ptr, bp);
        return;
    }
    //在链表中搜索第一个大小大于或等于新内存块大小的块
    while (GET_SIZE(HDRP(cur)) < bp_size && GET(NEXT_LINK_RP(cur))) {
        cur = GET(NEXT_LINK_RP(cur));
    }

    if (GET_SIZE(HDRP(cur)) >= bp_size) {
        // 获取前一个节点
        char* prev = GET(PREV_LINK_RP(cur));
        // 插入到cur之前
        PUT(NEXT_LINK_RP(bp), cur);
        PUT(PREV_LINK_RP(bp), prev);
        PUT(NEXT_LINK_RP(prev), bp);
        PUT(PREV_LINK_RP(cur), bp);
    }
    else {
        // 如果没有找到大小大于或等于新内存块大小的节点，bp则是最大结点，插入到末尾
        PUT(NEXT_LINK_RP(cur), bp);
        PUT(PREV_LINK_RP(bp), cur);
    }
}

//打印块信息，用于调试
static void printblock(void* bp)
{
    size_t hsize, halloc, fsize, falloc;

    checkheap(0);
    hsize = GET_SIZE(HDRP(bp));
    halloc = GET_ALLOC(HDRP(bp));
    fsize = GET_SIZE(FTRP(bp));
    falloc = GET_ALLOC(FTRP(bp));

    if (hsize == 0) {
        printf("%p: EOL\n", bp);
        return;
    }

    printf("%p: header: [%ld:%c] footer: [%ld:%c]\n", bp,
        hsize, (halloc ? 'a' : 'f'),
        fsize, (falloc ? 'a' : 'f'));
}

//检查单个块
static int checkblock(void* bp)
{
    int a1, a2, a3;
    //是否对齐
    a1 = ((size_t)bp % 8 != 0);
    if (a1)
        printf("Error: %p is not doubleword aligned\n", bp);
    //头和脚是否匹配
    a2 = (GET(HDRP(bp)) != GET(FTRP(bp)));
    if (a2)
        printf("Error: header of %p does not match footer\n", bp);
    //块大小是否合法
    size_t size = GET_SIZE(HDRP(bp));
    a3 = (size % 8 != 0);
    if (a3)
        printf("Error: %p payload size is not doubleword aligned\n", bp);
    //有一个不通过，返回0
    if (a1 || a2 || a3)
        return 0;
    else
        return 1;
}

//打印对应的空闲链表
static void printlist(void* bp, int size) {
    //如果该链表为空表
    if (bp == NULL) {
        printf("[listnode %ld] NULL\n", size);
        return;
    }
    void* header = bp;
    bp = GET(bp);
    while (bp != NULL) {
        printf("[listnode %ld] %p: header: [%ld:%c] prev: [%p]  next: [%p]\n",
            size, header, GET_SIZE(HDRP(bp)), (GET_ALLOC(HDRP(bp)) ? 'a' : 'f'), PREV_LINK_RP(bp), NEXT_LINK_RP(bp)
        );
        bp = NEXT_LINK_RP(bp);
    }
}

//检查空闲链表
static int checklist(void* bp, int size) {
    //空表是通过检查的
    if (bp == NULL) {
        return 1;
    }
    bp = GET(bp);
    void* pre = NULL;
    unsigned int csize, calloc;
    //遍历该链表的每个结点
    while (bp != NULL) {
        //该结点的前指针是否确实指向有效的结点
        if (pre != NULL && GET(PREV_LINK_RP(bp)) != pre) {
            printf("[%p]Error: pred point error\n", bp);
            return 0;
        }
        //前结点的后指针是否指向当前结点
        if (pre != NULL && GET(NEXT_LINK_RP(pre)) != bp) {
            printf("[%p]Error: next point error\n", bp);
            return 0;
        }
        csize = GET_SIZE(HDRP(bp));
        calloc = GET_ALLOC(HDRP(bp));
        //空闲链表中存在已分配的结点
        if (calloc == 1) {
            printf("[%p]Error : this node should be free\n", bp);
            return 0;
        }
        //链表中的空闲块是否按照从小到大的顺序排列
        if (pre != NULL && (GET_SIZE(HDRP(pre)) > csize)) {
            printf("Error: list size order error\n");
            return 0;
        }
        //检查结点的大小是否符合链表的大小
        if ((csize > size && size <= 8192) || (size > 8192 && csize < 8192)) {
            printf("[%d:%d]Error: list node size error\n", csize, size);
            return 0;
        }
        pre = bp;
        bp = GET(NEXT_LINK_RP(bp));
    }
}


/*
 * checkheap - 检查整个堆，verbose表示是否输出额外调试信息
 */
static int checkheap(int verbose)
{
    char* bp = heap_listp;
    if (verbose)
        printf("Heap (%p):\n", heap_listp);
    //检查序言块状态
    if ((GET_SIZE(HDRP(heap_listp)) != DSIZE) || !GET_ALLOC(HDRP(heap_listp)))
        printf("Bad prologue header\n");
    //检查序言快是否符合一般块的特点
    if (checkblock(heap_listp) == 0) {
        return 0;
    }
    //检查所有块
    char* prev_bp = bp;
    for (bp = NEXT_BLKP(prev_bp); GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (verbose)
            printblock(bp);
        //检查该块
        if (checkblock(bp) == 0) {
            return 0;
        }
        //存在两个连续的，未合并的空闲块
        if (GET_ALLOC(HDRP(prev_bp)) == 0 && GET_ALLOC(HDRP(bp)) == 0) {
            printf("Contiguous free blocks：%p and %p\n", prev_bp, bp);
            return 0;
        }
    }
    if (verbose)
        printblock(bp);
    //检查结尾块
    if ((GET_SIZE(HDRP(bp)) != 0) || !(GET_ALLOC(HDRP(bp)))) {
        printf("Bad epilogue header\n");
        return 0;
    }
    //检查所有空闲链表
    bp = block_list_start;
    int i = 0;
    for (; i < SIZE_SET_NUM; i++) {
        if (verbose)
            printlist(bp + i * WSIZE, 16 << i);
        if (checklist(bp + i * WSIZE, 16 << i) == 0) {
            return 0;
        }
    }
    return 1;
}

测试

./mdriver -f short1-bal.rep
./mdriver -f short2-bal.rep
./mdriver -V -t ./traces