Malloc Lab
注意，首先需要阅读教材，以及该项目仓库里面的指导手册
代码禁令
- 禁止使用标准库代码、示例代码直接提交
- 禁止任何全局数组、树、链表
- 禁止抄袭
为什么禁止使用全局数组？试想一下我们如果允许全局数组，那么直接在代码里声明一个 1GB 的数组，每次需要什么都直接从这个数组里给，那么根本不会涉及堆的分配，空间利用率甚至可以趋于正无穷，这显然是很离谱的。
在这个实验室中，您将为C程序编写一个动态存储分配器，即您自己版本的malloc、free和realloc例程，实现一个正确，高效和快速的分配器。本实验性能指标有两个方面，内存利用率和吞吐量，这两个方面都是动态存储分配器优秀与否的重要衡量指标，我们的分配器需要在吞吐量和内存利用率直接取得平衡以获取更高的分数。
本实验的代码中使用了大量的宏和指针，需要特别小心。此外，为方便调试程序以及便利地对比各个版本的差异，使用了宏进行条件编译
首先需要看明白《深入理解计算机系统(第三版)》597页的隐式空闲链表的实现，我们在这个基础上进行改进
为了获得到尽量高的分数，我们直接使用分离空闲链表来组织空闲块
下面是教材当中提到的基础宏
#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)))
隐式空闲链表
空闲块通过头部中的大小字段隐含地连接着的，分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的集合。
- 首次适配：从头开始搜索空闲链表，选择第一个合适的空闲块。
优点：它趋向于将大的空闲块保留在链表的后面；缺点：它趋向于在靠近链表起始处留下空闲块的“碎片”，这就增大了对较大块的搜索时间。 - 下一次适配：从上一次查询结束的地方开始进行搜索。
优点：下一次适配比首次适配运行起来明显要快一些，求其是当链表的前面布满了许多小的碎片时；缺点：然而下一次适配的内存利用率要比首次适配低得多。 - 最佳适配：检查每一个空闲块，选择适合所需请求大小的最小空闲块。
优点：最佳适配比首次适配和下一次适配的内存利用率都要高一些；缺点：然而，在简单空闲链表组织结构中如隐式空闲链表中，使用最佳适配的缺点是它要求对堆进行彻底的搜索，但更加精细复杂的分离式空闲链表组织，它接近于最佳适配策略，不需要进行彻底的堆搜索。
我们根据这一个基础的隐式空闲链表代码来修改。
/*
* 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)))
#define NEXT_FIT
/* 全局变量 */
static char* heap_listp = 0; /* 指向堆中第一个块 */
#ifdef NEXT_FIT
static char* rover; /* 下次适配指针 */
#endif
/*定义的辅助函数 */
static void* extend_heap(size_t words);//扩展堆，扩展words个字(4 byte)
static void place(void* bp, size_t asize);//
static void* find_fit(size_t asize);//查找空闲块
static void* coalesce(void* bp);//合并空闲块
static void printblock(void* bp);
static void checkheap(int verbose);
static void checkblock(void* bp);
//初始化堆
int mm_init(void)
{
/* 创建一个空的堆 */
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void*)-1) //申请四个字的堆
return -1;
PUT(heap_listp, 0); /* 堆的起始位置，值为0 */
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* 序言块头部，大小8字节，用来存放头和脚*/
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* 序言块脚部 */
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); /* 结尾块，大小为0，已分配*/
heap_listp += (2 * WSIZE); //指向序言快脚部
#ifdef NEXT_FIT
rover = heap_listp; //初始化下次适配指针
#endif
/* 扩展CHUNKSIZE这么多字节的初始堆， */
if (extend_heap(CHUNKSIZE / 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();
}
//如果size为0，返回空指针
if (size == 0)
return NULL;
/* 调整块大小以包括开销和对齐要求. */
if (size <= DSIZE)
asize = 2 * DSIZE; //8字节用来满足对齐要求，而另外8个用来放头部和脚部
else
asize = DSIZE * ((size + (DSIZE)+(DSIZE - 1)) / DSIZE); //加上开销字节(8字节)，然后向上舍人到最接近的8的整数倍。
//搜索空闲块
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize); //bp设为分配块，并分割
return bp;
}
//没有搜索到空闲块，则扩充堆，最少扩充CHUNKSIZE个字节
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
return NULL;
place(bp, asize); //bp设为分配块，并分割
return bp;
}
/*
* mm_free - 释放块
*/
void mm_free(void* bp)
{
if (bp == 0)
return;
//释放块的大小
size_t size = GET_SIZE(HDRP(bp));
if (heap_listp == 0) {
mm_init();
}
//填写这个块的头和脚
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
//与相邻块合并
coalesce(bp);
}
/*
* 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 */
return bp;
}
else if (prev_alloc && !next_alloc) { /* Case 2 */
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) { /* Case 3 */
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 { /* Case 4 */
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);
}
#ifdef NEXT_FIT
/* Make sure the rover isn't pointing into the free block */
/* that we just coalesced */
if ((rover > (char*)bp) && (rover < NEXT_BLKP(bp)))
rover = bp;
#endif
return bp;
}
/*
* mm_realloc - realloc实现
*/
void* mm_realloc(void* ptr, size_t size)
{
size_t oldsize;
void* newptr;
/* 如果 size == 0 释放这个块，并返回NULL. */
if (size == 0) {
mm_free(ptr);
return 0;
}
/* 如果传入的指针为NULL，则直接malloc. */
if (ptr == NULL) {
return mm_malloc(size);
}
newptr = mm_malloc(size);
/* If realloc() fails the original block is left untouched */
if (!newptr) {
return 0;
}
/* 复制原来数据. */
oldsize = GET_SIZE(HDRP(ptr));
if (size < oldsize) oldsize = size;
memcpy(newptr, ptr, oldsize);
/* 释放原来的块. */
mm_free(ptr);
return newptr;
}
/*
* mm_checkheap - 检查堆的正确性
*/
void mm_checkheap(int verbose)
{
checkheap(verbose);
}
/*
* 辅助程序函数
*/
/*
* extend_heap -扩展堆顶指针，共words * 4个字节，并考虑对齐
*/
/* $begin mmextendheap */
static void* extend_heap(size_t words)
{
char* bp;
size_t size;
/* 确定分配的字节数 */
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE; //line:vm:mm:beginextend
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL; //line:vm:mm:endextend
/* 将新分配的块设为为分配，并移动结尾块 */
PUT(HDRP(bp), PACK(size, 0)); /* Free block header */ //line:vm:mm:freeblockhdr
PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */ //line:vm:mm:freeblockftr
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */ //line:vm:mm:newepihdr
/* 如果前面的块是未分配，则合并 */
return coalesce(bp); //line:vm:mm:returnblock
}
/*
* place - 将大小为asize字节的数据块放置在空闲块bp的开始位置，
* 如果剩余部分至少达到最小块大小，则进行分割
*/
static void place(void* bp, size_t asize)
{
//原来的大小
size_t csize = GET_SIZE(HDRP(bp));
//如果达到最小块大小
if ((csize - asize) >= (2 * DSIZE)) {
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
}
//如果没有达到，不进行分割
else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
/*
* find_fit - 查找空闲块
*/
static void* find_fit(size_t asize)
{
#ifdef NEXT_FIT
/* Next fit search */
char* oldrover = rover;
/* Search from the rover to the end of list */
for (; GET_SIZE(HDRP(rover)) > 0; rover = NEXT_BLKP(rover))
if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover))))
return rover;
/* search from start of list to old rover */
for (rover = heap_listp; rover < oldrover; rover = NEXT_BLKP(rover))
if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover))))
return rover;
return NULL; /* no fit found */
#else
/* $begin mmfirstfit */
/* First-fit search */
void* bp;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
return bp;
}
}
return NULL; /* No fit */
#endif
}
//打印块信息，用于调试
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 void checkblock(void* bp)
{
if ((size_t)bp % 8)
printf("Error: %p is not doubleword aligned\n", bp);
if (GET(HDRP(bp)) != GET(FTRP(bp)))
printf("Error: header does not match footer\n");
}
/*
* checkheap - 堆一致性检查器
*/
void 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");
checkblock(heap_listp);
//检查所有空闲块
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (verbose)
printblock(bp);
checkblock(bp);
}
if (verbose)
printblock(bp);
//检查结尾块
if ((GET_SIZE(HDRP(bp)) != 0) || !(GET_ALLOC(HDRP(bp))))
printf("Bad epilogue header\n");
}
显式空闲链表
隐式空闲链表对于通用的分配器并不合适，因为块分配与堆块的总数呈线性关系，一种更好的方法是将空闲块组织为某种形式的显示数据结构。因为根据定义，程序不需要一个空闲块的主体，所以实现这个数据结构的指针可以存放在这些空闲块的主体。
这样使得分配时就不需要检查已分配的块，例如，使得首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。不过，释放一个块的时间可以是线性的（按照地址顺序来维护)，也可以是个常数(LIFO后进先出顺序），这取决于所选择的空闲链表中的排序策略。
分离空闲链表
书上介绍了两种基本的方法：简单分离存储和分离适配以及分离适配的一个特例伙伴系统。
下面使用书中介绍的分离适配来实现分配器。
分离适配：分配器维护着一个空闲链表的数组。每个空闲链表是和一个大小类相关联的，并且被组织成某种类型的显式或隐式链表。每个链表包含潜在的大小不同的块。这些块的大小是大小类的成员。有许多种不同的分离适配分配器。这里，我们描述了一种简单的版本。
为了分配一个块，必须确定请求的大小类，并且对适当的空闲链表做首次适配，查找一个合适的块。如果找到了一个，那么就(可选地)分割它，并将剩余的部分插入到适当的空闲链表中。如果找不到合适的块，那么就搜索下一个更大的大小类的空闲链表。如此重复，直到找到一个合适的块。如果空闲链表中没有合适的块，那么就向操作系统请求额外的堆内存，从这个新的堆内存中分配出一个块，将剩余部分放置在适当的大小类中。要释放一个块，我们执行合并，并将结果放置到相应的空闲链表中。
分离适配方法是一种常见的选择，C 标准库中提供的 GNU malloc 包就是采用的这种方法，因为这种方法既快速，对内存的使用也很有效率。搜索时间减少了，因为搜索被限制在堆的某个部分，而不是整个堆。内存利用率得到了改善，因为有一个有趣的事实:对分离空闲链表的简单的首次适配搜索，其内存利用率近似于对整个堆的最佳适配搜索的内存利用率。
在写代码之前，我们应该先看一下测试样例
(traces文件夹里面)
1. 文件
.rep原始轨迹文件-bal.rep原始轨迹的平衡版本文件
注：一个“平衡”的轨迹文件是指每个分配请求都有一个对应的释放请求。
2. 轨迹文件格式
轨迹文件是一个ASCII文件。它以一个4行的头部开始：
<sugg_heapsize> /* 建议的堆大小（未使用） */
<num_ids> /* 请求ID的数量 */
<num_ops> /* 请求（操作）的数量 */
<weight> /* 该轨迹的权重（未使用） */
头部之后是num_ops行文本。每一行表示一个malloc[a]、realloc[r]或free[f]请求。<alloc_id>是一个整数，用于唯一标识一个分配或重新分配请求。
a <id> <bytes> /* ptr_<id> = malloc(<bytes>) */
r <id> <bytes> /* realloc(ptr_<id>, <bytes>) */
f <id> /* free(ptr_<id>) */
例如，以下轨迹文件：
<文件开始>
20000
3
8
1
a 0 512
a 1 128
r 0 640
a 2 128
f 1
r 0 768
f 0
f 2
<文件结束>
是一个平衡的文件。它有一个建议的堆大小20000字节（被忽略），三个不同的请求ID（0、1和2），八个不同的请求（每行一个），以及一个权重1（被忽略）。
看懂这些，我们就可以自己调试了。如果测试结果里面，哪一个样例的分数低，就可以自己算一下内存利用率，然后自己设计调试。
首先添加一些专用的宏
//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);//检查一个空闲链表
初始化函数：
首先申请14个字，其中前11个用于存放空闲链表指针，2个为序言块，1个为结尾块，将heap_listp指向正确的堆块起始位置，然后扩展堆空间，作为初始空间。
初始并没有严格分配4096个因为在测试文件coalescing-bal.rep中，重复分配两个4095的块，添加上头脚开销后，要分配4104个，导致第一次给的初始大小并不够，所以要重新扩展两次4096大小的堆，然后又将两个块释放，申请8190大小的块，添加头脚后要8200，一共扩充了三次4096，但是只分配了8190导致内存利用率较低。
如果初始多扩充一些，可以正好在第一次不需要扩展堆，增加内存利用率。增加24个，是因为在realloc2-bal.rep样例中，也可以达到较大的内存利用率
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;
}
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);
}
free
释放bp指向的块
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);
}
realloc
如果直接释放原块，寻找新块会造成空间浪费
尝试能否在原地进行realloc：
- 原先size大小满足要求，直接返回原指针
- 判断下一个是否是空闲块，若是，空闲块的大小当前块的大小是否可以满足要求的size，若是就合并两个块。
- 判断下一个块为结尾块，就扩展。
- 再判断上一个块是否为空闲块，若是空闲块的大小当前块的大小是否可以满足要求的size，若是就合并两个块。
以上都不可行，再重新分配新的块
/*
* 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;
}
下面是辅助函数
查找空闲块
下面是查找空闲块的相关函数：
其中，按照size从小到大维护链表中的顺序，这样使用首次适配就相等于最佳适配。
find_fit:
- 确定在哪个链表中查找
- 遍历链表中的结点
- 使用首次适配
- 找不到合适的块返回空指针
//查找对应类的空闲链表
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);
}
/*
* 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;
}
为了实现 首次适配搜索 = 最佳适配的效果，我们必须要将每个链表按照size进行排序。
链表操作
_insert：
- 将要插入的块结点指针初始化为空指针
- 确定该块插入到哪个空闲链表
- 将块插入到空闲链表的合适位置（按照大小升序）
- 双向链表操作
_remove:
- 双向链表删除结点
// 插入到对应的位置
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 _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);
}
}
}
为了实现 首次适配搜索 = 最佳适配的效果，我们必须要将每个链表按照size进行排序。
合并空闲结点并插入
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;
}
分割块
place:如果剩余块大小≥最小块大小，则额外分割出一个空闲块并置入空闲链表
- 根据剩余大小确定是分割还是直接分配
- 如果是分割，有两种情况：分割出来的空闲块在前面还是后面
发现测试文件中{binary,binary2}-bal.rep交替分配一个大块和一个小块，然后释放所有小块，申请更大的大块。如果都采用一种方式，那么会导致内存利用率降低，因为大量空闲块无法合并，只能重新扩展堆。所以设置一个限界，当大于限界时，就是大块，放在后面，分出来的空闲块放在前面，反之。这样在刚才的情况中，就可以提高内存利用率了。
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));
}
//如果需要分配的块大小小于88，则把分割剩下的空闲块放在前面，分配块放在后面
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));
}
//如果需要分配的块大小大于88，则分配块在前面。
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;
}
扩展堆
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);
}
堆一致性检查
mm_check调用此函数即可
- 检查序言块，中间的所有块，结尾块
- 中间是否存在两个连续的未合并空闲块
- 检查每一个空闲链表
/*
* 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
}
检查单个块和单个空闲链表
checklist:
- 空表通过检查
- 遍历每个结点，检查前向指针，后向指针
- 检查是否存在已分配的结点在空闲链表中
- 检查是否按照从小到大排序
- 检查是否该链表的结点大小是否符合该链表
checkblock:
- 检查对齐，头脚匹配，大小是否为8的倍数
//检查空闲链表
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));
}
}
//检查单个块
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 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'));
}