说明：参考文献地址 A Malloc Tutorial
1 简介
malloc是干什么的？如果你连这个名字都没听过，那么你应该先去了解 Unix 环境下的 c 语言开发，然后再来阅读。对一个程序员而言，malloc是一个在 c 语言中用来分配内存的函数，但是大多数人并不知道它背后真正的原理，甚至有些人认为malloc是 c 语言的关键字或者认为它是系统调用。事实上，malloc是一个再简单不过的函数而已，而且只需要很少的操作系统相关知识就可以让我们彻底理解它的原理。
下面来一步步的实现一个简单的malloc函数，从而帮助我们理解其背后运作的原理。因为仅仅作为说明原理之用，所以这里实现的malloc不会太高效，但是足以说明原理。
什么是 malloc
malloc(3)是一个用来分配内存块的标准的 c 语言库函数。它遵循以下规则：
malloc至少分配所需字节数的内存；malloc返回其所分配内存空间(程序可以成功读写的空间)的指针；- 一块内存一旦被
malloc分配，其他malloc调用不能再分配该内存块的任何部分，除非指向该内存块的指针被释放掉； malloc应该是可控的：他必须能够很快完成分配并返回；malloc同时应该提供重新分配内存块大小和释放内存的功能
malloc函数必须遵循以下原型：
void *malloc(size_t size);
其中size是所需要的内存大小。如果失败（没有足够的内存空间可以分配），应该返回NULL。
2 堆，brk 和 sbrk 系统调用
在开始实现第一个malloc函数之前，需要了解内存在大多数多任务操作系统中是如何管理的。这里我们只是做出一个抽象的解释，从大体上去帮助理解，至于很多细节，它们都依赖操作系统原理和硬件相关的知识。
2.1 进程的内存
每个进程都有自己的虚拟地址空间被 MMU（Memory Management Unit, 内存管理单元）(和内核)动态的转换到物理内存地址空间。这部分空间被划分成了几个部分，我们需要了解的是至少有一部分空间存放代码，一个用来存放局部变量的栈，一部分用来存放常量和全局变量的空间，以及程序的无组织空间我们称之为堆。
堆是一个连续的（依据虚拟地址而言）内存空间，它有三个边界：一个起始点，一个最大限度边界（通过 sys/ressource.h 中的 getrlimit(2)函数和 setrlimit(2)函数来管理）和一个被称为break的结束点。break标记了隐射内存空间的结束，也就是说，虚拟地址空间部分对应着真实的内存空间。下图表示内存组织结构
要想实现一个malloc函数，我们需要知道堆的起始点和 break 的位置，然后我们来移动 break。要做到这些，就需要用到两个系统调用，brk和sbrk。
2.2 brk(2)和 sbrk(2)
我们可以在这些系统调用的文档中看到相关描述：
int brk(const void *addr);
void *sbrk(intptr_t incr);
在 linux 系统中使用man 2 brk命令查看文档
brk() and sbrk() change the location of the program break, which defines the end of the process’s data segment (i.e., the program break is the first location after the end of the uninitialized data segment). Increasing the program break has the effect of allocating memory to the process; decreasing the break deallocates memory. brk() sets the end of the data segment to the value specified by addr, when that value is reasonable, the system has enough memory, and the process does not exceed its maximum data size (see setrlimit(2)). sbrk() increments the program’s data space by increment bytes. Calling sbrk() with an increment of 0 can be used to find the current location of the program break. On success, brk() returns zero. On error, -1 is returned, and errno is set to ENOMEM. On success, sbrk() returns the previous program break. (If the break was increased, then this value is a pointer to the start of the newly allo‐cated memory). On error, (void *) -1 is returned, and errno is set to ENOMEM.
我们将使用sbrk作为主要工具来实现一个malloc函数。所要做的事情就是获取更多的空间(如果需要的话)去满足调用者的需求。
2.3 Unmapped Region and No-Man’s Land
正如前面讲到的 break 标记了映射虚拟地址空间的结束：越过 break 来访问地址会造成总线错误。maximum limit 和 break 之间的剩余地址没有被系统的虚拟内存管理器关联到物理内存。 但是，如果你了解一点关于虚拟内存的知识，那么你会知道内存是通过 page 来映射的：物理内存和虚拟内存是组织在具有固定大小的 page 中(大多数情况下)。page 的大小圆圆超过 1byte(在大多数操作系统中，page size 是 4096bytes)。也就是说，break 有可能没有恰好落在 pages 的边界上。
上图展示了带有 page 边界的内存组织结构。我们可以看到 break 没有对齐到 page 的边界。那么处于 break 和下一个 page 边界之间的内存是一种什么样的状态呢？事实上，这段空间是可以访问的！你可以在这段空间里读写字节。问题是，你对下一个 page 边界的位置没有任何线索，你可以依赖操作系统来找到它，但是这是一个不好的建议。
这些 no-man’s land 通常是 bug 的根源：一些对堆外指针的错误操作大多数只有小测试的情况下都能成功，只有当操作很大量的数据的时候会失败。
2.4 mmap(2)
尽管我们在本文中不会用到mmap(2)系统调用，但是我们仍然需要花时间去了解它。它有一个匿名模式(mmap(2)通常被用来直接的在内存中映射文件)可以用来(完整地或者在某些特殊情况下)实现malloc函数。
mmap(2)在匿名模式下可以分配特定的记忆体空间，而munmap可以将其释放。这通常比传统的基于sbrk的 malloc 要更简单和高效。一些 malloc 实现使用mmp来分配较大的空间(超过一个 page)。OpenBSD 的 malloc 函数只使用mmap，加上一些方法以提高安全性。
3 实现一个简陋的 malloc
首先，我们将要使用sbrk(2)来实现一个简陋的 malloc。这个 malloc 可能是最烂的一个，但是也是最简单，实现起来最快的一个。
3.1 原理
原理非常的简单，每当malloc被调用的时候，我们将 break 移动所需字节的空间，然后返回异动前 break 的地址。看起来是不是很简单，这样只需要 3 行代码就可以实现，但是这样的话我们无法实现释放和重新分配的功能。
3.2 实现
#include <sys/types.h>
#include <unistd.h>
void *malloc(size_t size)
{
void *p;
p = sbrk(0);
if (sbrk(size) == (void *)-1)
return NULL;
return p;
}
4 堆
在上一节中，我们花了点时间实现了一个简单的 malloc 函数，但是并不能满足所有的需求。因此本节我们将尝试着去了解堆从而实现一个更加高效的 malloc 函数，进而实现 free 和 realloc。
4.1 我们需要什么
如果我们考虑编程环境之外的问题，我们可以推断出什么样的信息能解决我们的问题。让我们来做个比喻：你拥有一块区域，然后划分它其中的一部分租出去。客户要求不同的尺寸(你划分的时候都是按照同一个的标准)而且还要是连续的。当他们使用完了退回给你，然后你又可以接着租出去。
在这片领域的一边有一条路，路上有一辆可以编程的车：你可以输入区域和目的地之间的距离。我们需要知道每一块是从哪里开始的（这就相当于 malloc 返回的指针）。
一个解决方案是我们标记每一个下一部分开始的地址（和当前部分的大小以避免不必要的计算）。我们也将空闲的部分打上标记（当客户使用完返还的时候做上标记）。此时，当有客户想要一个确定大小的区域的时候我们坐车遍历一个个标记。当我们发现一个区域被标记为空闲状态而且能够满足客户的需求的时候，我们去掉空闲的标记然后租给客户。如果我们到了最后一个区域（这个区域的标记没有指向下一个区域的地址）我们只需要到这个区域的末尾添加一个新的标记。
我们可以把上述的思想转换到内存中：在每一个内存块的开始部分需要有额外的信息，其中包括内存区块的大小，下一个区块的地址和当前区块是否为空闲状态。
4.2 如何表示块信息
我们需要的仅仅是在每一个 chunk 的开始需要有一个很小的 block 来保存额外的信息，这个信息被称为 meta-data。这个 block 至少需要包含一个指向下一 chunk 的指针，一个标记当前 chunk 是否为 free 的标记以及当前 chunk 的可存放的 data size。当然，这个 block 在 malloc 函数返回的指针前面。
上图展示了一种分配的 block 前带有 meta-data 信息的堆的组织结构。每一个 chunk 都包含一个存放 meta-data 的 block 和一个存放数据的 block。malloc 函数返回的指针指向的是存放数据的 block，而不是整个 chunk。
那么，我们该如何把它转换成 c 代码呢？上述思想看起来很像一个传统的链表，于是我们写了一个链表：
typedef struct s_block *t_block;
struct s_block {
size_t size;
t_block next;
int free;
};
说明：使用typedef可以简化自定义类型的使用。考虑到我们使用该类型的时候都是基于指针的形式，所以在typedef中将s_block定义为t_block类型的指针，这对链表来说会是一个很好的体验，因为链表是一个指针，而不是一个 block（一个空链表就是一个空指针）。
将 flag 设置成 int 类型看起来很浪费空间，但是由于结构体是默认对齐的，所以改变 flag 的类型对结构体占用空间没有任何影响。待会我们会看到我们将如何来压缩 meta-data 的 size。此外还需要注意的一点就是 malloc 必须返回对齐的地址。
一个被问的很频繁的问题是：在没有 malloc 的情况下我们如何创建一个结构体？The answer is simple.你只需要知道一个结构体到底是什么就好了。在内存中，一个 struct 仅仅是其字段的串联，所以在上述例子中，struct s_block只是 12bytes(32 bit integer)，第一个 4bytes 指的是size这个字段，第二个 4bytes 指的是next这个字段，最后一个指的是free这个字段。当编译器遇到访问 struct 字段(例如 s.free 或 p->free)的情况时，它会将其转换成 struct 的基地址加上它前面字段的长度(p->free ==> _((char _)p+8), s.free ==> _((char _)&s + 8))。你需要做的就是用sbrk分配足够的空间。
/* Example of using t_block without malloc */
t_block b;
/* save ths old break in b */
b = sbrk(0);
/* add the needed space */
/* size is the parameter of malloc */
sbrk(sizeof(struct s_block) + size);
b->size = size;
5 malloc 的第一个优化版
在这一节当中我们将实现第一个传统 mallc 的优化版。第一个优化算法非常简单：我们遍历 chunks 列表直到我们发现一个 free 的 block 而且有足够的空间来满足需求。
5.1 指针对齐
指针常常需要按照整型来对齐。这里我们只考虑 32bit 的情况，64bit 原理相同。因此，指针必须能被 4(32 bits = 4 bytes)整除。meta-data block 已经对齐了，那么我们唯一需要做的事情就是使得 data 的 size 对齐。
首先，我们来玩玩数字游戏：任取一个正整数，先整除 4，然后再乘以 4，这样就得到了最近的一个能被 4 整除的且比 4 小的数字，如果要得到最近的一个能被 4 整除且大于 4 的数字就再加上一个 4。
任取一个正整数$x$，
\[ x = 4 \times p + q, q \in \left[0, 3\right] \]
如果$x$是 4 的倍数，那么
\[ q = 0, x - 1 = 4 \times \left(p - 1\right) + 3, \left(\left(x - 1\right) / 4 \right) \times 4 + 4 = 4 \times p = x \]
如果$x$不是 4 的倍数，那么
\[ q \not= 0, x - 1 = 4 \times p + \left(q - 1\right), q - 1 \in \left[0, 2\right]; \]
所以：
\[ \left(x - 1\right)/4\times4+4 = 4 \times p + p = x/4\times4+4 \]
于是我们得到了一个公式:
\[ \left(x - 1\right) / 4 \times4 + 4 \]
那么，我们怎样用 c 语言来表示呢？首先，跟 4 做乘法和除法可以被表示成左位移和右位移运算(«和»)，它比普通的运算要高效很多。因此我们的公式在 c 语言中可以写成：
((x-1)>>2)<<2 + 4
要想得到一个正确的宏，我们需要添加一些额外的括号：
#define align4(x) (((((x)-1)>>2)<<2)+4)
5.2 查找 chunk:第一个优化算法
查找一个标记为 free 的且又空间富裕的 chunk 是如此的简单：我们开始在堆的基址(程序中会保存，待会我们会看到)检验当前的 chunk，如果它能满足需求，我们只需要返回它的地址即可，否则我们继续下一个 chunk 直到我们找到了满足需求的 chunk，或者到了堆末尾也没找到。唯一的技巧就是保存最后一次访问的 chunck，因此如果我们没有找到满足需求的 chunk 的话，malloc 函数可以很容易到达堆的末尾。代码是如此的明了，base 是一个指向堆的起始位置的指针：
t_block find_block(t_block *last, sizt_t size)
{
t_block b = base;
while (b && !(b->free && b->size >= size)) {
*last = b;
b = b->next;
}
return (b);
}
这个函数返回一个满足需求的 chunk，或者没有合适的就返回 NULL。每一次循环之后，last 变量就会指向上一次访问的 chunk。
5.3 扩展堆
假如我们总是找不到合适的 chunk，有时候(尤其是在程序刚开始的时候使用 malloc)我们需要扩展堆。这也是相当简单的一件事：我们移动 break，然后初始化一个新的 block，当然我们需要更新最后一个 block 的 next 字段(实际上就是给链表中添加一个结点)。
在接下来的开发中，我们需要在s_block结构体的 size 上做一些小技巧，于是定义了一个宏来获取 meta-data block 的 size，现在这个宏的定义如下：
#define BLOCK_SIZE sizeof(struct s_block)
这些代码平淡无奇，我们只是在sbrk调用失败的使用返回 NULL(我们并没有尝试着去理解为什么)。我们同样不能确定sbrk返回的是上一次的 break，我们仅仅是先保存它然后再移动它。我们可以用last和last->size来计算。
t_block extend_heap(t_block last, size_t s) {
t_block b;
b = sbrk(0);
if (sbrk(BLOCK_SIZE + s) == (void *)-1)
return NULL;
b->size = s;
b->next = NULL;
if (last)
last->next = b;
b->free = 0;
return b;
}
5.4 blocks 分裂
你可能已经意识到我们使用的是第一个满足需求的 block 而没有考虑它的 size(假如空间非常富裕呢)。如果我们这样做的话，那么我们会浪费掉很多空间(想象一下，你需要 2bytes，然后找到了一个 256bytes 的 block)。第一个解决方案就是分裂 blocks：当一个 chunk 比需要的空间大很多的时候，我们在链表中插入一个新的 chunk。
下面的函数只有在空间可以被访问的情况下才会被调用。使用的 size 也必须是对齐的。在这个函数里，我们将做一些指针的算术操作，为了防止错误发生，我们将使用一些小技巧来确保我们的操作在 1byte 的误差范围内（内存 p+1 依赖于 p 指向的类型）。
我们仅仅在结构体 s_block 中增加了一个字符数组类型的成员。结构体的末尾存在一个简单的数组：数组被放在结构体的末尾，对于我们而言，数组的指针就是 meta-data 的结束。c 语言禁止使用长度为 0 的数组(在 c99 之前)，所以我们定义了一个长度位 1 的字符数组，这也是我们为什么定义了一个代表 s_block 结构体 size 的红的原因。
**说明：**此处使用到了Flexible array member技巧，该技巧在 c 语言开发中应用非常广泛，例如在 php 内核的 hash table 实现中也用到了，具体可参考鸟哥的博客：深入理解 PHP 之数组(遍历顺序)
struct s_block {
size_t size;
t_block next;
int free;
char data[1];
};
#define BLOCK_SIZE 12 // 3 * 4
这个扩展并不需要对 extend_heap 做任何修改，因为新的字段并没有被直接使用。
至此我们来实现split_block函数：该函数通过参数来把 block 切割成一个所需要的 size。
void split_block(t_block b, sizt_t s) {
t_block new;
new = b->data + s;
new->size = b->size - s - BLOCK_SIZE;
new->next = b->next;
new->free = 1;
b->size = s;
b->next = new;
}
在上述的第三行代码中使用b->data来做指针运算。因为 data 是字符数组类型，我们可以肯定的是误差精确到一个字节范围内。
5.5 malloc 函数
好了，至此我们可以实现我们的 malloc 函数了。其实就是对前面所实现的函数的包装。我们需要将传入的 size 对齐，然后如前面所描述的那样检测我们是不是第一次调用 malloc 函数。
首先别忘了 5.2 节中的函数find_block使用到了一个全局变量base。该变量的定义如下：
void *base = NULL;
这是一个void类型的指针，而且被初始化为NULL。malloc 函数首先需要做的事情就是检验base，如果为NULL则说明这是第一次调用，否则开始前面描述的算法：
- 查找一个 free 状态的且有足够空间的 chunk;
- 如果我们找到了：
- 尝试着分割这个 block(需要的空间 size 和找到的 block 的 size 的差值足够存放 meta-data 和一个最小的 block(4bytes))
- 将该 chunk 标记为使用状态(b->free = 0)
- 否则：我们扩展堆
关于last变量的使用说明：find_block函数将最后一次访问的 chunk 的指针存放到last中，所以我们可以在扩展堆的时候使用它，从而避免遍历整个 list。
- 否则：我们扩展堆（此时堆为空）
void *malloc(size_t size) {
t_block b, last;
size_t s;
s = align4(size);
if (base) {
last = base;
b = find_block(&last, s);
if (b) {
/* can we split */
if ((b->size - s) >= (BLOCK_SIZE + 4))
split_block(b, s);
b->free = 0;
} else {
/* No fitting block, extend the heap */
b = extend_heap(last, s);
if (!b)
return NULL;
}
} else {
/* first time */
b = texted_heap(NULL, s);
if (!b)
return NULL;
base = b;
}
return b->data;
}
6 calloc, free 和 realloc 函数
6.1 calloc
说明：malloc(2),calloc(3)这种函数括号中带有数字表示的是函数在系统的 man page 中章节数，通常 Linux 系统章节数遵循以下约定：
1、Standard commands (标准命令) 2、System calls (系统调用) 3、Library functions (库函数) 4、Special devices (设备说明) 5、File formats (文件格式) 6、Games and toys (游戏和娱乐) 7、Miscellaneous (杂项) 8、Administrative Commands (管理员命令)
calloc(3)也非常的简单：
- 首先用正确的 size(两个操作数的产物)来调用 malloc;
- 将 block 中的每个 byte 都设置为 0.
这里我们又使用到了一些小小的技巧：data block 的 size 通常是 4 的倍数，因此将迭代的步长设置为 4bytes。为此，我们使用一个新的指针作为一个 unsigned integer 类型的数组。下面是实现的代码：
void *calloc(size_t number, size_t size) {
size_t *new;
size_t s4, i;
new = malloc(number * size);
if (new) {
s4 = align4(number * size) << 2;
for (i = 0; i < s4; i++)
new[i] = 0;
}
return new;
}
说明：
- 此处 unsigned integer 类型长度为 4bytes 是针对 32 位操作系统，在 64 位系统中已经不适用；
- 因为 new 经过 4bytes 对齐后是 4 的倍数，所以其等于长度为
number * size / 4的 unsigned integer 类型的数组，数组的每一个元素都有 4bytes，也就是说遍历数组的时候步长实际为 4bytes.
6.2 free
快速实现一个free(3)函数是很容易的，但是却不那么实用。我们有两个问题需要解决：一个是查找到要被释放的 chunk，另一个是避免空间碎片。
6.2.1 碎片：malloc 函数的诟病
malloc 函数存在一个主要的问题就是碎片：经过几次 malloc 和 free 调用之后，我们把堆划分成了很多很小的 chunks，每一个 chunk 都很小不足以满足较大的 malloc 分配，但是所有的 chunks 加起来却能满足。这个问题被称作空间碎片问题。虽然不对算法进行修改我们无法阻止由于算法造成的额外碎片，但是我们可以避免其他碎片的来源。
当我们选择了一个空间比所需空间大很多的空闲 chunk 的时候，我们分隔它。虽然这样做能够更有效的利用内存(新的 chunk 能够被接下来的分配所使用)，但是却产生了更多的碎片。
一个限制碎片的解决方案是合并被释放的 chunks。当我们释放一个 chunk 的时候，如果与它相邻的 chunk 也是释放状态，那么我们将他们合并成一个较大的 chunk。我们需要做的仅仅是检查当前 chunk 的上一个 chunk 和下一个 chunk。但是如何找到上一个 chunk 呢？下面列举了一些解决方案：
- 从起始位置开始查找，会特别慢(尤其是我们已经做了一次查找被释放 chunk 的操作)
- 如果我们已经做了查找当前 chunk 的操作，我们可以将上次访问的 chunk 的指针保存起来(就像 find_block 函数中那样)
- 将链表改为双向链表
我们选择了最后一个方案，因为它很简单，而且可以让我们使用一些技巧来查找目标 chunk。因此我们再次修改我们的 struct s_block，但是由于我们还有其他的修改(见下一节)，所以我们将会在后边的修改中呈现其代码。
于是，我们现在要做的就是合并操作。我们首先实现一个简单的合并函数来合并 chunk 和它的后继(注：前驱，后继，都是链表中的术语)结点。合并前驱结点同理。在下面的代码中我们使用新的字段prev来表示前驱结点。
t_block fusion(t_block b) {
if (b->next && b->next->free) {
b->size += BLOCK_SIZE + b->next->size;
b->next = b->next->next;
if (b->next)
b->next->prev = b;
}
return b;
}
合并的原理很清晰：如果下一个 chunk 为 free，我们将两个 chunk 的 size 相加，然后再加上 meta-data 的 size 并赋值给当前 chunk 的 size。接着我们将当前 chunk 的后继指向当前结点后继的后继结点，如果这个结点存在的话，将其前驱结点设置为当前结点。
6.2.2 查找正确的 chunk
另一个释放操作的问题是如何高效，正确的查找被 malloc 分配的 chunk。要实现就需要解决下面的问题：
- 校验传入的指针是否真的是 malloc 返回的指针；
- 查找 meta-data 指针
我们可以通过范围检测快速排出掉大多数无效指针：如果指针超出了堆的范围，那么就是无效指针。对于没有被排出的指针，我们如何来确保他就一定是被 malloc 返回的呢？
一个方法是在 block 结构体中加入一些特殊的数字。一个很好的特殊数字就是使用它自身的指针：我们加入一个ptr字段指向该结构体的 data 字段，如果b->ptr == b->data，那么 b 很可能就是能够被 free 操作释放的 block。下面是扩展后的结构体：
struct s_block {
size_t size;
struct s_block *next;
struct s_block *prev;
int free;
void *ptr;
char data[1];
};
typedef struct s_block *t_block;
/* Get the block from an addr */
t_block get_block(void *p) {
char *tmp;
tmp = p;
return (p = tmp -= BLOCK_SIZE);
}
/* valid addr for free */
int valid_addr(void *p) {
if (base) {
if (p > base && p < sbrk(0) {
return (p == (get_block(p))->ptr);
}
}
return 0;
}
6.2.3 free 函数
free 函数的流程为：首先校验指针然后的到相应的 chunk，将其标记为 free，如果可以的话，进行合并。如果在堆的末尾，我们还要对内存进行释放。
释放内存的操作也是非常简单的：如果在堆的末尾，我们只需要通过简单的调用brk(2)将 break 移动到 chunk 的起始位置。
- 如果指针通过校验：
- 获取 block 的地址
- 如果前驱结点存在而且 free，移动到前一个 block 并将这两个 blocks 合并
- 同样的操作来合并后继结点
- 如果是最后一个 block，那么释放内存
- 如果已经没有 block 了，那么回到最开始的状态(将 base 设置为 NULL)
- 如果指针没有通过校验，不需要做任何操作
void free(void *p) {
t_block b;
if (valid_addr(p)) {
b = get_block(p);
b->free = 1;
if (b->prev && b->prev->free)
b = fusion(b->prev);
if (b->next)
fusion(b); //此处之所以这么写请看fusion函数的实现就会明白
else {
if (b->prev)
b->prev->next = NULL;
else
base = NULL;
brk(b);
}
}
}
6.3 通过 realloc 函数调整 chunk 的大小
realloc(3)函数和calloc(3)一样很简单。基本上我们只需要多做一个内存拷贝的操作而已。这里我不想用系统提供的memcyp函数，因为我们可以做一个更好的。
void copy_block(t_block src, t_block dst) {
int *sdata, *ddata;
size_t i;
sdata = src->ptr;
ddata = dst->ptr;
//用到了前面的技巧，用整型数组，使得移动的步长为4bytes(32位系统)
for (i = 0; i * 4 < src->size && i * 4 < dst->size; i++) {
ddata[i] = sdata[i];
}
}
一个很天真却有用的 relloc 只需要遵循以下算法规则：
- 使用 malloc 分配一个新的大小为给定 size 的 block
- 拷贝 data
- 释放之前的 block
- 返回一个新的指针
当然，我们想更高效一些：如果我们有足够的空间的话，就不希望再做一个新的分配操作。不同之处在于：
- 如果 size 没有改变，或者额外的空间满足需要，即使有少量多余的空间也不足以分割，那么不做任何操作
- 如果缩小 block，那么做分割操作
- 如果后继 block 是 free 状态，而且能够提供足够的空间，那么合并他们，如果可能的话尝试做分割操作
下面就是具体的代码实现。不过需要注意的是，realloc(NULL, s)这样的调用是合法的，而且会被替换成malloc(s)调用。
void *realloc(void *p, size_t size) {
size_t s;
t_block b, new;
void *newp;
if (!p) {
return malloc(size);
}
if (valid_addr(p)) {
s = align4(size);
b = get_block(p);
if (b->size >= s) {
if (b->size - s >= BLOCK_SIZE + 4)
split_block(b, s);
} else {
if (b->next && b->next->free && (b->size + BLOCK_SIZE + b->next->size) >= s) {
fusion(b);
if (b->size - s >= BLOCK_SIZE + 4)
split_block(b, s);
} else {
newp = malloc(s);
if (!newp)
return NULL;
new = get_block(newp);
copy_block(b, new);
free(p);
return newp;
}
}
return p;
}
return NULL;
}
6.3.1 FreeBSD 的 reallocf 函数
FreeBSD 提供了另一个 realloc 函数：realloc(3)函数会在重新分配失败的情况下释放掉原来的指针。
void *reallocf(void *p, size_t size) {
void *newp;
newp = realloc(p, size);
if (!newp)
free(p);
return newp;
}
6.4 总结
现在已经修改好了 block 结构体，我们只需要重写split_block函数和extend_heap函数，并重新定义BLOCK_SIZE。
struct s_block {
size_t size;
struct s_block *next;
struct s_block *prev;
int free;
void *ptr;
char data[1];
};
typedef struct s_block *t_block;
//定义block的size，因为使用sizeof调用的话会将最后一个data[1]也计算进来，
//实际上这个字段没有占用空间
//注意：在c99之后，直接使用char data[]，就不需要此定义，直接使用sizeof即可
#define BLOCK_SIZE 20;
//仅仅是简单的双向链表操作而已
void split_block(t_block b, size_t s) {
t_block new;
new = (t_block)(b->data + s);
new->size = b->size - s - BLOCK_SIZE;
new->next = b->next;
new->prev = b;
new->free = 1;
new->ptr = new->data;
b->size = s;
b->next = new;
if (new->next)
new->next->prev = new;
}
//在堆尾添加一个结点，如果操作失败返回NULL
t_block extend_heap(t_block last, size_t s) {
int sb;
t_block b;
b = sbrk(0);
sb = (int)sbrk(BLOCK_SIZE + s);
if (sb < 0)
return NULL;
b->size = s;
b->next = NULL;
b->prev = last;
b->ptr = b->data;
if (last)
last->next = b;
b->free = 0;
return b;
}
7 问题和优化
通过从无到有实作一个 malloc 让我们对计算机程序的的内存分配和管理有了更深的理解，知道了产生内存碎片的原因以及如何去优化。然而此实作存在很多不足，主要表现为以下几点：
- 原文是基于 32 位系统实现的，所以后期可以将其优化为同时兼容 32 位和 64 位系统
- 原文中使用的 Flexible array member 是基于 c99 之前的写法，可以优化为 c99 支持的写法
- 原文中使用的
brk和sbrk已经过时
评论