MyMalloc

项目总览

在本项目中，你需要在给定框架下使用 C 语言编写一个动态存储分配器，也就是实现你自己的 malloc、free 和 realloc。

我们推荐您在给定框架下实现隐式自由块链表的 First fit 算法，保证正确性即可

对于有能力有追求的同学，可以尝试实现隐式链表，并实现 First fit、Next fit、Best Fit 等算法，比较并优化你的 malloc

或者你也可以尝试实现隔离存储的链表，设计你自己的匹配算法

开始之前

如果你还不清楚 malloc 是什么，如何使用 malloc

请阅读：https://zh.cppreference.com/w/c/memory/malloc

如果你还不清楚 malloc 是如何运作的

请阅读 basic note

本实验改编自 CSAPP 课程的 lab，如果你想体验原汁原味的抓狂体验或者想要实现更接近底层更高效的内存分配器

请使用 CSAPP 课程网站资源：https://csapp.cs.cmu.edu/3e/labs.html

项目概述

mm.c

这是你需要修改完善的，并且是本项目初始自带的文件中你唯一可以修改的文件，不要修改其余文件，也不要修改该文件中不需要修改的部分

你的主要目标是完善四个函数，实现他们的功能，并获取更高的分数

int mm_init(void)

评测开始时，会调用该函数，你可以在该函数中实现程序的初始化，例如申请初始空间，初始化链表等

返回值为 0 表示正常初始化

void *mm_malloc (size_t size)

传入申请空间大小 size，返回指向符合需求的空间的 void * 指针

void mm_free (void *ptr)

传入需要释放的空间的起始地址，不需要返回值

通过该函数的传入信息用你的方式维护你的结构体链表

void mm_realloc(voidptr, size_t size)

传入原数据所在空间地址 void* ptr、新的空间区域大小 size

1. 如果 ptr 为 NULL，此调用等价于 mm_malloc (size)
2. 如果 size 为 0，此调用等价于 mm_free (ptr)
3. 否则，为其重新分配一片空间并继承原数据，若新空间大小小于原空间大小，则继承靠前的数据（警惕数据污染）

mm.h

可以修改该文件为你的代码提供支持，不修改该文件也可完成该项目

mdriver.c

用于测试你的程序正确性，不要修改该文件，你不会用到其中的成员

traces

默认的测试数据集，不要修改该文件夹下的文件，你可以按照规范添加自己的测试数据，并使用 mdriver 的命令行参数运行自创数据集

fsecs.c/h clock.c/h fcyc.c/h ftimer.c/h

与计时相关，不要修改该文件，你不会用到其中的成员

memlib.c/h

与堆栈空间分配相关，不要修改该文件，你会用到其中的一些成员函数

mem_sbrk

传入需要扩展的空间的大小 incr，在原空间的基础上在堆栈上申请新空间，可以视作连续的空间

void *mem_heap_lo(void)

返回指向当前堆栈最前部的指针

void *mem_heap_hi(void)

返回指向当前堆栈最后部的指针

size_t mem_heapsize(void)

返回当前堆大小（单位：字节）

检验程序

在项目目录下运行 make 生成可执行文件 mdriver

可执行文件 mdriver 接受以下命令行参数：

1. -t <tracedir> 使用指定文件夹下测试数据
2. -f <tracefile> 使用指定文件作为测试数据
3. -h 打印命令行参数说明
4. -l 同时运行 C 标准库中的 malloc，但是不统计其空间利用率
5. -v 输出详细数据
6. -V 输出更详细的数据

校验程序对以下事项提出正确性要求：

1. 你分配的块必须与字节对齐，也就是你分配的块的地址必须是 8 的倍数
2. 你分配的块不能超过当前分配的堆的大小
3. 分配的块之间不能有重叠
4. realloc 需要正确继承数据

当 mdriver 输出错误信息时，你可以打开 mdriver.c 寻找错误信息的来源已经对应的注释来获取信息

编程事项

1. 不要定义任何新的全局变量或静态变量
2. 出于简化难度的目的，你可以使用 malloc，但是请在必要用的地方使用并记得 free
3. 不要修改你不应该修改的东西

提示

一致性检查

此处一致性特指行为一致性，也就是说你应当检查你的程序的行为是否符合预期

一致性检查会降低程序运行的效率，但是对你的调试大有裨益，你可以在通过测验程序之前保持一致性检查的进行

错误的假设是调试的痛苦根源 😭

你可能需要对一下事项进行一致性检查：

1. 释放的空间得到了正确的维护吗？废弃的空间会导致你的空间利用率下降，这或许不会引发错误但这是严重的问题
2. 相邻的自由块得到了合并吗？没有合并的自由块不仅会降低你的空间利用率 (明明能分配但是没分配) 还会降低你的时间效率
3. 每个区块都在你的链表中吗，区块之间是否存在重叠（提示：你可以通过检查相邻地址之差是否与块大小匹配）

单元测试

单元测试是软件开发过程中的一种测试方法，旨在验证软件中最小可测试单元（通常是函数、方法或类）的正确性。

对成熟的项目而言，进行单元测试是必须的。

想象一下，当项目的运行结果偏离预期时，你拥有一百个组件。

哪怕其中只有三个组件出错，排查定位时也存在$(\genfrac{}{}{0ex}{}{3}{100})$ 种可能性。

因此，在你完成一个组件时立刻对其进行功能测试，能大大降低 DEBUG 的开销。

本项目为你提供了一些现成的简单的单元测试，我们鼓励你针对自己代码潜在的问题撰写自己的单元测试。

警告 ⚠️: 通过单元测试并不意味着你的函数实现是绝对正确的

每个人的实现都不一样，你可能需要自行设计单元测试

如果你需要设计自己的单元测试，你可能需要了解这个。

打开同目录下 mtest.c 阅读注释了解更多。

善用 gdb

调代码切忌我以为、我认为、这应该

我们 C 语言没有任何 bug，一切以实际运算为准

当代码崩溃时，如果无法通过一致性测试和调试输出找到错误，请使用 gdb。

因为你有可能犯了一个极为基本的错误，比如数组越界，解引用空指针，gdb 擅长找到这样的错误。

让我们开始吧

对于代码能力良好的同学，可以直接打开 mm.c，阅读代码注释，尝试完成本项目

你可以阅读 guide，参考函数实现思路，使用现成的单元测试辅助项目完成

Basic note

什么是虚拟内存（Virtual Memory）

如上图所示，我们可以将计算机中的虚拟内存视作一根条状物，下方为低地址处，上方为高地址处

虚拟内存的大小仅与你的系统类型有关（如 64 位系统与 32 位系统的最高地址不同）

这样的特性消弭了硬件上的差距，使得工程师不用为特定的硬件设计特定的程序，这样消除硬件差距，用抽象性统一程序的设计在计算机系统中比比皆是

当然，虚拟内存的设计还有许多妙用，例如它让所有程序都认为自己拥有独立的内存空间，感兴趣的同学可以自行学习 CSAPP 第九章内容，此处不再展开

虚拟内存中的堆与栈

从高地址向低地址扩展，这是我们熟悉的栈，用于存储局部变量、函数参数、返回地址等。

而自低地址向高地址扩展的，则是堆，用于分配连续空间给程序使用，如全局数组。

这里的 “堆” 与数据结构中的 “堆” 并不相同，前者是虚拟内存中一片区域的称呼，后者是一种树状数据结构。

因为前者与 “栈” 同属于一片区域，且在功能上有一定相似性，常被人们合称为堆栈，但是我并不喜欢这个词汇，大多数时候只会带来歧义与误解，除了。。。

笑点解析：这张牌英文原名就是 Stack

堆空间的动态分配

除了编译时就已经确定的空间大小（静态初始化），对于剩余的堆空间以及程序随运行给出的不同需求，我们需要一个分配器，大致分为两种：显式分配器与隐式分配器。这二者都需要显式地去分配块，但对分配内存这一事情的行为主体有所区别。

#include <stdio.h>
#include <stdlib.h>
int main(void) {
  // 1. 整型数组
  int *intArray;
  int size = 5;
  intArray = (int *)malloc(size * sizeof(int)); // 分配5个整数大小的内存空间
  free(intArray); // 释放整型数组内存空间
  // 2. 字符串数组 (字符指针数组)
  char **stringArray;
  size = 3;
  stringArray = (char **)malloc(size * sizeof(char *)); // 分配3个字符指针大小的内存空间
  free(stringArray); // 释放字符串指针数组空间
  // 3. 结构体数组
  struct Student {
    char name[20];
    int age;
  };
  struct Student *studentArray;
  size = 2;
  studentArray = (struct Student *)malloc(size * sizeof(struct Student)); // 分配2个结构体大小的内存空间
  free(studentArray); // 释放结构体数组空间
  return 0;
}
/*
可以发现，malloc的空间大小是用户根据所需大小手动申请，最终的类型也是用户类型转换得到的。
*/

隐式分配器的典型便是 Java，他将内存分配的行为主体交给了程序，用户只要描述自己的需求，便能得到一片动态申请的空间（当然出于静态类型语言的要求，你依旧要指定指向这片内存区域的指针类型，出于面向对象的特性，你往往会比 C 拥有更多的选择类型），并且 Java 中的数组如果是通过 new 关键字来申请，其大小随时可以改变。程序会自动侦测不再被使用的内存块，并将其回收，这一过程被称作垃圾回收（Garbage Collection）。

public class ArrayDemo {
  public static void main(String[] args) {
    // 动态分配：使用 new 关键字创建数组，在堆内存中分配空间
    int[] arr1 = new int[5]; // 初始化大小为 5 的数组
    // 大小可变：使用 Arrays.copyOf() 方法将数组扩容到 10
    arr1 = Arrays.copyOf(arr1, 10);
  }
}

内存分配器

内存分配器的行为

在不同的系统上，对分配器有着不同的要求，下文中，我们假设内存分配器需要对双字对齐。字大小采用 x86-64 定义，为 16bit。

如上图所示，内存分配器根据程序指令进行了以下行为：

• 申请四字空间，p1 指向这片空间
• 申请五字空间，p2 指向这片空间，但是分配器最终分配了六字（因为五字不行）（保证内存空间对齐）
• 申请六字空间，p3 指向这片空间
• 释放 p2 所指的块，注意此时并没有清空指针 p2 的值，p2 依旧指向一片处于未利用状态的空间区域
• 申请二字空间，p4 指向这片空间，此时 p2 与 p4 指向同一个位置

注意到，分配器要做的事情非常简单，只需要返回满足大小需求的未占用空间的地址即可。理论上你可以写一个天底下最烂的内存分配器 —— 每次都返回最靠近尾部的空闲地址，放不下就向系统申请内存空间。

因此，我们要对好的分配器下定义，学习分配器设计的限制与好的分配器的追求。

内存分配器的限制

标准通用的分配器存在诸多限制，分配器不仅要为不同程序服务，还要对多个程序服务。

• 不能对操作的顺序做任何假设，不能假设这个块之后会被 free 所以先 malloc 给某个程序
• 不能离线处理操作，必须在线立即处理操作。意思是，你不能积攒你收到的请求然后按最适合你分配器实现的方式排序，然后再执行
• 保证你的块按照对齐标准对齐（在本项目中，向 8bit 对齐）
• 不能修改已分配的块，也就是说不能移动已分配的块

内存分配器的追求

在上述约束条件下，分配器的设计者追求在两个相互冲突的指标之间寻求平衡：吞吐量与内存利用率。二者所代表的分别是时间效率与空间效率。

吞吐量指单位时间内完成的分配请求（malloc 与 free）数量。

单独提高这个指标并不难，例如上述那个” 天底下最烂的内存分配器 “在这个指标上大概能薄纱所有主流分配器。

而内存利用率则是指在你的分配器整个运行过程中，所有时刻中已分配块的合计大小的最大值与运行结束后堆大小的比。也就是你越充分利用了整个堆空间，这项指标越高。

更多的时候，内存分配器的开发者对后者更为在意，那么，是什么导致堆空间总是无法得到充分利用呢

碎片

我们称堆空间没有得到充分利用的现象为碎片（Fragmentation） 碎片分为内部碎片（Internal fragmentation）与外部碎片（External fragmentation）

内部碎片

内部碎片是指堆栈实际剩余空间加起来也无法满足空间申请需求，因此被迫扩展堆大小，这是可以量化且显而易见的，如果你能够减少外部碎片，一般而言内部碎片也会随之减少。

外部碎片

外部碎片则是因为你的分配器给出的分配方案不够理想造成的，例如现在需求一块八字空间，但是只有两块空闲的四字空间，虽然从内部碎片的角度来看并没有产生内部碎片，但是由于无法分配八字空间，堆空间依旧被迫扩大造成浪费。

针对外部碎片，大多数分配器选择少而大的空闲空间，而不是多而小的空闲空间。这是一种启发式的思路，也就是给算法定义出什么是” 优秀 “的情况，并让算法以达成这种情况为目的运行。

内存分配器的结构

显然，面对这样的问题，我们需要一些数据结构

这个数据结构要解决两个基本问题：

• 如何找到可分配的空闲块？
• 在释放区块后如何将区块合并，并保持算法原有性质？

对于一些基础良好的读者，他可能会想，我能不能用线段树或者平衡树这样的高级数据结构来解决这个问题，这似乎在时间和空间上都极度优越

然而，我们要考虑到，维护堆空间分配的数据结构也是堆空间的一部分（虽然在本实验中我们不要求将维护使用的数据跳过抽象层直接写入堆空间，但事实上这些数据都将计入你的空间成本），也就是说使用越复杂的数据结构去维护内存分配器，天然地会扩大内存分配器的内部碎片与外部碎片

那么，有没有一个简洁的数据结构能解决这个问题呢？

事实上，作为大多数程序员接触的第一个数据结构，链表就能解决这个问题，下面，我将介绍本次实验使用的隐式链表第一顺位优先算法的思路

算法设计

隐式链表

同目录下的 mm.h, 有如下对链表节点的声明：

/*块结构体*/
struct Block {
  // 指向前一个块的指针，没有则为NULL
  struct Block *pre;
  // 指向后一个块的指针，没有则为NULL
  struct Block *nxt;
  // 块所对应的堆空间起始地址
  void *ptr;
  // 块所占堆空间大小
  size_t size;
  // 0:块不处于占用状态 1:块处于占用状态
  int empty;
};
typedef struct Block block;
// 头指针，指向链表中第一个块
extern block *head;
// 尾指针，指向链表中最后一个块
extern block *tail;

使用头指针与尾指针指向当前链表的头和尾

我们记录每一块的前一块和后块，保证遍历和增删的可维护性

对于块本身，我们记录块所对应的空间的起始位置的指针，块管理的空间大小已经块为空或非空

如上图，所有块无论空与非空都记录在链表中，作为内存分配器的关键信息 —— 空闲块，隐式的存在于该链表中，所以称为隐式链表

对于该链表结构，在本项目中，我们需要他实现以下功能：

• 寻找剩余空间充裕的空闲块
• 将空闲块的空间进行分配，可能插入新块，维护它（们）的信息
• 向堆申请更多空间，并将该空间用块维护
• 将占用状态的块释放，维护它的信息
• 将相邻的空闲块合并

First fit

显然，在申请空间的时刻，满足该空间需求的块可能有多个，那么我们的算法该如何找到这样块，以什么标准优先选择怎样的块

在本项目中，我们使用 First fit 优先算法

从链表头开始，顺序遍历，当找到可用的空闲块，立刻返回该块的信息

Guide

阅读同目录下 mtest.c 中的注释了解单元测试的使用方法

如果你认为你需要一些辅助与提示完成该项目，请阅读下文

我们鼓励你在不阅读下文的情况完成该项目

（当然我们鼓励你使用预设的单元测试，减少一些你的机器劳作）

Task1—— 遍历链表

在本 Task 中，你需要完成 mm.c 中的函数: find_fit 与 find_by_ptr

find_fit

功能描述

传入需分配的空间的大小 size

顺序遍历当前链表

当找到满足要求的块时返回指向该块的指针

否则返回空指针

实现思路

顺序遍历链表，检查块的 empty 和 size 属性

find_by_ptr

功能描述

传入指向堆空间地址的指针 ptr

顺序遍历链表

返回指向该地址的块（维护该空间地址信息的块）的指针

实现思路

顺序遍历链表，检查块的 ptr 属性

Task2—— 分配空间

在本 Task 中，你需要完成 mm.c 中的函数: place

place

功能描述

传入空闲块指针 bk ，传入分配空间大小 size

将空闲块指针 bk 靠前的 size Byte 空间标记为已分配

修改原空闲块的信息

为新的占用块分配块结构体进行维护

维护链表的前驱后继

返回分配空间的起始地址

实现思路

考虑创建新的块结构体维护分配后处于被占用状态的空间

更新块结构体的相关属性

提示

• 注意 size 和 bk 的 size 恰好相同的情况
• 注意 bk 为头指针所指块的特殊情况
• 你可以对指针进行算数运算，以推算剩余的空闲堆空间的起始地址
• 对指针解引用前请注意其是否可能为空指针

Task3—— 合并空闲块

在本 Task 中，你需要完成 mm.c 中的函数: coalesce

coalesce

函数功能

传入空闲块指针 bk

将该空闲块与相邻的空闲块合并

返回指向合并后的块的指针

函数思路

你可能需要考虑四种情况：

• 前无空块后无空块
• 前无空块后有空块
• 前有空块后无空块
• 前有空块后有空块

具体的步骤类似传统双端队列的删除节点

但是在该项目中你需要维护 ptr 和 size

提示

• 你仍旧需要在对指针解引用前确认其是否为空指针
• 在完成代码后，四种情况的代码可能会有所重复，你可以使用更少的条件控制语句实现该函数吗
• 注意特判头指针和尾指针的转移情况
• 注意释放不再使用的块结构体指针

Task4—— 申请空间

在本 Task 中，你需要完成 mm.c 中的函数: extend_heap

extend_heap

函数功能

传入需要向堆空间申请的空间大小 size

将申请得到的空间用 block 结构体并接入链表尾部

函数思路

使用项目提供的 mem_sbrk 向堆申请空间

使用块结构体维护新空间的信息

将块插入链表末尾

提示

• 向结尾插入一个新的空闲块，我们可能需要做什么事情？
• 注意特判当前链表为空的情况

TaskFin—— 完成项目

在需要完成的函数中对上述已经实现的函数进行简单的调用

对状态进行一些基本处理

这个项目便大功告成了

make 后运行 mdriver 试试吧

相信无需阐述、无需提示、无需预设的单元测试（当然我们鼓励你自己去写一个）

你已经有能力完成这个项目

加油💪胜利就在眼前🏆