# malloc_lab

**Repository Path**: nononoGitee/malloclab

## Basic Information

- **Project Name**: malloc_lab
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 211
- **Created**: 2024-12-08
- **Last Updated**: 2024-12-08

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# malloc实验

## 实验目的

在这个实验中，您将编写一个用于C程序的动态存储分配器，即您实现独立实现的malloc、free和realloc函数。鼓励你以创造性的方式进行探索设计，并实现一个正确、高效和快速的分配器。

## 内存分配器实现

你所实现的动态存储分配器将由以下四个函数组成，这些函数在mm.h中声明并在mm.c中定义。

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

我们提供的mm.c文件实现了我们能想到的最简单但仍然功能正确的malloc包。以这个作为起点，修改这些函数（可能还要定义其他私有的静态函数），使它们遵守以下语义：

* mm_init：在调用mm_malloc、mm_realloc或mm_free之前，应用程序（即将用于评估实现的基准程序mdriver.c）调用mm_init来执行任何必要的初始化，例如分配初始堆区域。如果在执行初始化时出现问题，则返回值应为-1，否则为0。

* mm_malloc：mm_malloc例程返回一个指向至少大小为size字节的分配块有效负载的指针。整个分配的块应该位于堆区域内，并且不应与任何其他分配的块重叠。我们将比较你的实现与标准C库（libc）中提供的malloc版本。由于libc的malloc总是返回对齐到8字节的有效负载指针，因此您的malloc实现也应该这样做，并始终返回对齐到8字节的指针。

* mm_free：mm_free例程释放ptr指向的块。它不返回任何内容。只有当传递的指针（ptr）是由先前的mm_malloc或mm_realloc调用返回的，并且尚未被释放时，此例程才保证可工作。

* mm_realloc：mm_realloc例程返回一个指向至少大小为size字节的分配区域的指针，并且具有以下约束条件。

  * 如果ptr为NULL，则调用等效于mm_malloc(size)；
  * 如果size等于零，则调用等效于mm free(ptr)；
  * 如果ptr不为NULL，则它必须是由先前的mm_malloc或mm_realloc调用返回的。mm_realloc调用将ptr指向的内存块（旧块）的大小更改为size字节，并返回新块的地址。请注意，新块的地址可能与旧块相同，也可能不同，这取决于你的实现、旧块中的内部碎片量以及realloc请求的大小。在旧块和新块大小的最小值范围内，新块的内容与旧ptr块的内容相同。其余部分为未初始化状态。例如，如果旧块为8字节，新块为12字节，那么新块的前8字节与旧块的前8字节相同，而最后4字节未初始化。类似地，如果旧块为8字节，新块为4字节，那么新块的内容与旧块的前4字节相同。

以上函数的语义应与的libc中的malloc、realloc和free例程的语义一致。在shell中键入man malloc可以获取完整的文档资料。

## 堆一致性检查器（辅助调试）

动态内存分配器是极具挑战性的程序，因为它们涉及大量的无类型指针操作，很难正确且高效地编程。编写一个堆检查器来扫描堆并检查其一致性将非常有帮助。堆检查器可能检查的一些示例包括：

* 每个空闲链表中的块是否标记为free？
* 是否存在任何未经合并的连续空闲块？
* 每个空闲块实际上是否都在空闲列表中？
* 空闲列表中的指针是否指向有效的空闲块？
* 已分配的块是否存在重叠现象？
* 堆块中的指针是否指向有效的堆地址？
  
堆检查器在mm.c中的函数mm_check中实现，函数原型如下：
```C
int mm_check(void)
```

它将检查所有的一致性条件。仅当堆是一致检查通过时，它才返回非零值。在一致性检查时，你可以不受限于以上给出的建议，也不必必须实现以上所有建议的检查。当mm_check失败时，建议打印出错误消息。

这个一致性检查器是在开发过程中进行调试的。当你提交mm.c时，请确保删除或注释掉所有对mm_check的调用，因为它们会降低您的吞吐量指标。对于你提交的mm_check函数，老师将会给予主观评分。请确保添加注释并记录您正在检查的内容。

## 例程库函数

memlib.c包实现了动态内存分配器的模拟内存系统。您可以在程序中调用memlib.c中的以下函数：

* void *mem_sbrk(int incr)：扩展堆，其中incr是一个正的非零整数，并返回指向新分配的堆区域第一个字节的通用指针。其语义与Unix的sbrk函数相同，不同之处在于mem_sbrk只接受正的非零整数参数。
* void *mem_heap_lo(void): 返回指向堆中第一个字节的通用指针。
* void *mem_heap_hi(void): 返回指向堆中最后一个字节的通用指针。
* size_t mem_heapsize(void): 返回堆的当前大小（以字节为单位）。
* size_t mem_pagesize(void): 返回系统的页面大小（以字节为单位，在Linux系统上为4K）

## 测试基准程序

程序mdriver.c可以测试你实现的mm.c的正确性、空间利用率和吞吐量。程序由一组跟踪文件驱动控制，这些文件包含一系列分配、重新分配和释放指令，指示驱动程序以某种顺序调用您的mm_malloc、mm_realloc和mm_free例程。评分时，我们将使用相同的驱动程序和跟踪文件来评估你提交的mm.c文件。

驱动程序mdriver.c接受以下命令行参数：
* -t <tracedir>: 在目录tracedir中查找默认跟踪文件，而不是使用config.h中定义的默认目录。
* -f <tracefile>: 使用特定的跟踪文件进行测试，而不是使用默认的一组跟踪文件。
* -h: 打印命令行参数的摘要。
* -l: 同时运行并测量libc的malloc，和你自己实现的malloc。
* -v: 详细输出。为每个跟踪文件打印性能分析报告，以紧凑的表格方式打印。
* -V: 更详细的输出。在处理每个跟踪文件时打印额外的诊断信息。在调试期间很有用，可以确定哪个跟踪文件导致您的malloc包失败。

## 编程规范

* 不应更改mm.c中的任何接口。
* 不应调用任何与内存管理相关的库调用或系统调用。不能再你的代码中使用malloc、calloc、free、realloc、sbrk、brk或这些调用的任何变体。
* 不允许在mm.c程序中定义任何全局或静态复杂数据结构，如数组、结构、树或列表。但是，你可以在mm.c中声明全局标量变量，如整数、浮点数和指针。

## 评价

如果违反任何规则或你的代码存在错误并导致测试程序崩溃，将获得零分。

否则，您的评分将按以下方式计算：


* 正确性（20分）。如果你的解决方案通过测试程序的正确性测试，您将获得满分。其中每个正确trace都将获得部分分数。

* 性能（35分）。将使用两个性能指标来评估你的实现：
  * 空间利用率：测试使用的内存总量（即通过mm_malloc或mm_realloc分配但尚未通过mm_free释放的内存）与您的分配器使用的堆大小之间的峰值比率。最佳比率等于1。你应该找到良好的策略来最小化碎片的问题，以使此比值尽可能接近最佳值。
  * 吞吐量：每秒完成的平均操作数。

测试程序通过计算性能指数 $P$ 来计算您的分配器的性能，该指数是空间利用率和吞吐量的加权和。

$$ P = wU + (1 − w)min(1, \frac{T}{T_{libc}})$$

其中，$U$ 是空间利用率，$T$是吞吐量，而$T_{libc}$是在默认trace下libc的malloc的吞吐量。性能指标更倾向于空间利用率而不是吞吐量，其中$w$的默认值为0.6。

由于内存和CPU时间都是重要的系统资源，我们采用这个公式来鼓励你对内存利用率和吞吐量进行平衡优化。理想情况下，性能指数将达到$P = w + (1 − w) = 1$即100%。由于每个指标最多分别对性能指数贡献w和1 − w，因此你不应过于极端地优化仅内存利用率或仅吞吐量。要获得良好的分数，必须在利用率和吞吐量之间取得平衡。

* 主观分数（10分）
  
 * 您的代码应该分解为函数，并尽可能少地使用全局变量。

 * 您的代码应以一个头部注释开头，描述您的空闲块和已分配块的结构，空闲链表的组织方式，以及您的分配器如何操作空闲链表表。每个函数应该在一个头部注释之前，描述该函数的功能。  

 * 每个函数都应该有一个头部注释，描述它的功能和实现方式。

 * 实现堆一致性检查器mm_check，且有良好的注释。

堆一致性检查器实现，得5分，良好的程序结构和注释，得5分。

## 提交

提交malloc-handin.zip文件（在每次make后会自动生成）和实验报告

## 提示


* 在初始开发阶段，请使用mdriver -f选项。使用小型跟踪文件将简化调试和测试。我们已经包含了两个这样的跟踪文件（short1,2-bal.rep），可以用于初始调试。

* 使用mdriver的-v和-V选项。-v选项将为您提供每个跟踪文件的详细摘要。-V还将指示何时读取每个跟踪文件，这将有助于您排查错误。
  
* 使用gcc -g编译并使用调试器。调试器将帮助您隔离和识别超出边界的内存引用。

* 仔细阅读教材中“malloc实现”小节的内容。教材上有一个基于隐式空闲列表的简单分配器的详细示例。以其作为出发点。在你完全理解简单的隐式列表分配器之前，请不要开始编码工作。

* 在C语言的宏中封装指针计算。因为需要进行大量的类型转换， 内存管理器中的指针计算很容易混淆和出错。通过实现宏完成指针操作，可以显著降低复杂性。参见教材中的示例。

* 将你的实现分阶段进行。前9个跟踪包含对malloc和free的请求。最后2个跟踪包含对realloc、malloc和free的请求。我们建议首先确保malloc和free例程在前9个跟踪上能够正确高效地工作。然后再将注意力转向realloc的实现。开始阶段，可以在现有的malloc和free实现的基础上构建realloc。但是要获得真正良好的性能，您需要构建一个独立的realloc函数。

* 使用gprof性能分析工具，帮助你优化程序性能。
  
* 编写一个高效的malloc函数需要虽然代码很有限。然而，我们可以保证，这将是你迄今为止编写的最困难和复杂的代码之一。所以，请尽早开始。