malloc的故事

发表于 更新于

读了张洋的《如何实现一个malloc》和Marwan Burlle的《A Malloc Turorial》，张洋的博文是对Marwan Burlle的理解、翻译和补充，缺失了一些细节。但读了张洋的文章后，再读《A Malloc Turorial》会快很多。

#A Malloc Tutorial

讲了什么

  1. 什么是malloc
  2. 堆的内存模型
  3. 如何通过系统调用操纵堆
  4. 什么是块、块的数据结构
  5. 结构体的本质（虽然变量data属于结构体，但只是想获取数据区的指针，而数据区不属于meta结构体）
  6. 如何实现内存对齐
  7. 基本的堆管理需要哪些功能/函数
  8. 如何创建、选择、分割块
  9. 碎片整理（融合块）
  10. free要做什么，如何实现
  11. 如何实现calloc
  12. 何时把块“还给系统”
  13. realloc的原理，及优化

没讲什么

  1. 如果free时，不还块会怎样。
  2. BLOCK_SIZE大小是如何确定的。
  3. 何时，如何分配大块的内存，mmap。
  4. realloc分配超大时，就要与mmap交互。
  5. 如何对自己编写的内存管理测试。

张洋的博文

与《A Malloc Turorial》重复的项不再列出。

讲了什么

  1. 虚地址与物理地址、缺页处理
  2. 进程的内存布局
  3. 堆内存的生长方向

没讲什么

  1. free中删除最后一个节点

我的理解和补充

针对《A Malloc Turorial》和张洋的《如何实现一个malloc》做一些解释和补充：

  1. malloc的返回值类型是void*代表了，返回的是一个指针，但不确定是什么类型，所以使用前要强制转换。
  2. man malloc指出：
    1. malloc申请的大小大于MMAP_THRESHOLD(128KB)时，内存的分配会自动使用`mmap。
    2. glibc为了支持多线程应用，使用了互斥信号量，来避免内存管理冲突。
    3. glibc为了提高多线程应用的性能，使用了Arena allocation.
    4. 如果malloc，calloc，realloc失败，应当设置errno为ENOMEM，否则和errno相关的某个库程序会挂掉。
    5. malloc，calloc，realloc崩溃，多半是由heap冲突引起的，比如溢出了分配的chunk(块)，或同一个指针释放两次。
  3. MSDN指出：在Windows中，一个进程可以有多个heap，最初的那个被称为默认堆。

block是什么？

在glibc中被称为chunk，其中的实现与这里的不太一样，嗯……相似不大。关于chunk更详细的解释就在源码里时光机。

为了管理堆内存，我们把内存分成很多大块，这些大块大小不一定相等。一个大块分成两部分，一个是块头（block），一个是块尾（data）。块尾就是我们要分配给用户用的空间，即malloc返回的空间。块头存放的是描述信息（meta data），描述的是块尾的信息，比如，它的大小，状态（可用性、读写性），开始位置，为了管理所有的块，让块都连起来，所以还需要链表的指针（如果使用链表管理的话），为了让块头满足内存对齐，我们还需要一些填充位。

块中有个字段叫data，它记录了块尾的起始位置，但实际上它不能占用块头的大小，听起来是不是矛盾，理解了结构体的内存布局，和指针的访问方式，这个问题就迎刃而解了。既然它不属于块头，那为什么把它定义到结构体里呢？

  1. 为了方便访问块尾。如果没有data字段，每次访问一个块的块尾大致需要这样：b + BLOCK_SIZE，其中b为块头的指针，每次都这样去访问块尾，不是很闹心吗？！（glic用宏实现）
  2. 为了方便移动指针和计算指针间的距离。内存是按字节分配地址的，而char类型刚好占一个字节，所以把data声明为char，所以在上面做运算可以得到正确的内存地址。b是s_block类型的，那么b + BLOCK_SIZE也是s_block类型的，每次还需要强制转化为char*才能移动指针或计算，不是很折腾吗！？

但这也带来了一个问题：不能使用sizeof获取BLOCK_SIZE。

sizeof返回的实际占用的内存大小，因此在计算过程中，会执行内存对齐的计算。而在block的定义中，包含了字段data，内存对齐后，会多出一些。所以，需要手动设置BLOCK_SIZE。

至于什么时候建造一个块，不同的管理方案，自然不同。在这里，当前的块不足以满足要求时，就从未用的堆内存中，建造一个块。

另外，你如何实现sizeof呢？

1
#define sizeof(obj) ((char*)(&obj + 1) - (char*)(&obj))

为什么BLOCK_SIZE 是 24？

注意BLOCK_SIZE块头的大小，前面提到，data其实不属于block，而又为了能够让block的指针访问它，所以把他加到了block里的定义。block占用的内存空间是size，next，free，padding占用的内存空间，size_t占用8B，指针占用8B，int占用4B，共24B，所以BLOCK_SIZE 是 24。

为什么需要padding？不浪费内存吗？

关键还在内存对齐。块头和块尾都需要各自对齐，因此，block的data字段应该在一个对齐单元的开始位置，而不应当处于block所占用的内存区，所以如果block的成员不能刚好对齐，那么需要设置填充位，而padding就是这个填充位。

如果因为不使用padding而造成block和data区有重叠，就更不能愉快的使用内存了。 CPU读内存时一次读对齐的8个字节，data的开始位置，在中间，还怎么愉快的读？一次能读出来的数据，现在要分两次，CPU的时间，远比内存的时间金贵，所以，以空间换时间，这不是浪费。

为什么分裂的最低阀值是BLOCK_SIZE+8?

需要BLOCK_SIZE的必要block，剩下的为data区，data区又要字节对齐，在以8字节对齐的机器上，所以剩余的空间至少是BLOCK__SIZE+8。

free如何确定是已经分配过的指针

块头（meta区）设置一个magic ptr，指向data，根据用户传入的指针p，得到block的指针，如果block->ptr刚好等于p，那么是我们曾经分配的，否则不是。

BLOCK_SIZE应当改为32。

free碎片如何处理？

改成双向链表，如果相邻的空间为free，那么合并（fusion）。如果不是双链表，我们只能向后合并，造成仍然有大量碎片。

代码汇总

Gist

参考资料

  1. 原始资料：A Malloc Tutorial
  2. 张洋博文，如何实现一个malloc：
    http://blog.codinglabs.org/articles/a-malloc-tutorial.html
  3. 没有A Malloc Tutorial简洁，也是简单示例：《C标准库》
  4. glic malloc源码，就算读注释，也会豁然开朗：
    [1]. http://repo.or.cz/w/glibc.git/blob/HEAD:/malloc/malloc.h
    [2]. http://repo.or.cz/w/glibc.git/blob/HEAD:/malloc/malloc.c
  5. malloc和free仍然存在较多问题的，所以另许多程序员头疼，《C语言接口与实现》讲述了如何进一步封装。PS，高级部分使用了arena。
  6. Windows堆内存管理：https://msdn.microsoft.com/en-us/library/ms810603.aspx

未看

  1. 扩展阅读：
    • Linux 内存管理：内存映射，主要讲mmap： http://blog.jobbole.com/91891/
    • 什么是堆和栈（翻译自SO）：http://blog.jobbole.com/75321/
    • Linux内存点滴，用户进程内存空间。结合将了malloc和操作系统层面的内存管理，但文中也是有错误的，比如L4，L5（访问free的指针）执行，free后，那段空间可能并没有还给OS，因此页表中还存在映射，不会出现段错误，但如果还给了OS，页表中映射被取消，再去访问，才出现错误。：http://blog.jobbole.com/45733/
    • 那些数据结构与算法在Linux内核中的使用：http://blog.jobbole.com/52669/