calloc 实现_自实现malloc_malloc实现细节(5)

首先我们在结构体中增加magic pointer（同时要修改BLOCK_SIZE）：

然后我们定义检查地址合法性的函数：

当多次malloc和free后，整个内存池可能会产生很多碎片block，这些block很小，经常无法使用，甚至出现许多碎片连在一起，虽然总体能满足某此malloc要求，但是由于分割成了多个小block而无法fit，这就是碎片问题。

一个简单的解决方式时当free某个block时，如果发现它相邻的block也是free的，则将block和相邻block合并。为了满足这个实现，需要将s_block改为双向链表。修改后的block结构如下：

合并方法如下：

有了上述方法，free的实现思路就比较清晰了：首先检查参数地址的合法性，如果不合法则不做任何事；否则，将此block的free标为1，并且在可以的情况下与后面的block进行合并。如果当前是最后一个block，则回退break指针释放进程内存，如果当前block是最后一个block，则回退break指针并设置first_block为NULL。实现如下：

为了实现realloc，我们首先要实现一个内存复制方法。如同calloc一样，为了效率，我们以8字节为单位进行复制：

然后我们开始实现realloc。一个简单（但是低效）的方法是malloc一段内存，然后将数据复制过去。但是我们可以做的更高效，具体可以考虑以下几个方面：

如果当前block的数据区大于等于realloc所要求的size，则不做任何操作

如果新的size变小了，考虑split

如果当前block的数据区不能满足size，但是其后继block是free的，并且合并后可以满足，则考虑做合并

下面是realloc的实现：

以上是一个较为简陋，但是初步可用的malloc实现。还有很多遗留的可能优化点，例如：

同时兼容32位和64位系统

在分配较大快内存时，考虑使用mmap而非sbrk，这通常更高效

可以考虑维护多个链表而非单个，每个链表中的block大小均为一个范围内，例如8字节链表、16字节链表、24-32字节链表等等。此时可以根据size到对应链表中做分配，可以有效减少碎片，并提高查询block的速度

可以考虑链表中只存放free的block，而不存放已分配的block，可以减少查找block的次数，提高效率

还有很多可能的优化，这里不一一赘述。下面附上一些参考文献，有兴趣的同学可以更深入研究。

这篇文章大量参考了A malloc Tutorial，其中一些图片和代码直接引用了文中的内容，这里特别指出

Computer Systems: A Programmer's Perspective, 2/E一书有许多得参考的地方

关于Linux的虚拟内存模型，Anatomy of a Program in Memory是很好的参考资料，另外作者还有一篇How the Kernel Manages Your Memory对于Linux内核中虚拟内存管理的部分有很好的讲解

对于真实世界的malloc实现，可以参考glibc的实现

本文写作过程中大量参考了维基百科，再次感谢这个伟大的网站，并且呼吁大家在手头允许的情况下可以适当捐助维基百科，帮助这个造福人类的系统运行下去

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-35441-5.html