流行分配器dlmalloc剖析之：设计理念

流行分配器dlmalloc剖析之：设计理念

版权声明： 本文章由vt.buxiu发布在,版权归vtzone研究小组所有，转载请保持此声明！！！

@@内容摘要：doug lea malloc的设计理念，大部分内容来自doug lea本人的dlmalloc说明@@局部性改善依赖于局部性原理：应用同一时刻请求的内存块，倾向于有相同的用途，并倾向于具有相同的生命周期。具有好的局部性，将可以减少内存页面切换，提高处理器的缓存命中率，这对应用可能产生很大的性能改善。

如果单考虑局部性改善，分配器可以每次都分配距离上次分配最近距离的内存块满足应用，这就是所谓的nearest-fits（与best-fits）类 似，但这种策略会导致严重的碎片。因此，在dlmalloc实现时，在于其他目标冲突最小的时候使用了next-fits：只有当请求的size对应的 chunk不存在，并且最近一次分割出来的chunk正好满足或大于这次请求的大小的时候，将上次分割出来的chunk用来满足这次请求(如果还是大于这 次请求，则进行分割)；否则还是使用best-fits进行查找bins。由于next-fits比best-fits要快，这种方法改善了 dlmalloc的平均分配时间，并且这种严格限制条件的使用next-fits，改善了这次请求正好与上次分割出来size完全匹配没被马上使用的情 况。
Wilderness内存块Wilderness chunk指其边界是进程heap最高点的那个chunk，由于wilderness可以通过brk(Unix/Linux)进行任意的扩展(除非系统内 存耗尽brk失败)或缩小。如果把wilderness和其他chunk一样对待，则可能其他chunk还可以满足请求的时候就使用了 wilderness，这就增加了可能调用brk向系统获得更多内存的机会，造成更严重的内存消耗。
Dlmalloc对wilderness chunk特殊对待，将其作为一个bigger chunk,作为best-fits的扩展，只有当其他chunk不能满足的请求的时候才用wilderness满足应用请求。进一步避免了严重内存消耗。
内存映射除 了通过调用brk系统调用接口扩展进程的heap大小之外，大多数Unix操作系统都提供了mmap系统调用，为应用分配一块不连续的内存区域(这里指多 次连续调用mmap获得内存之间的不连续，一次调用mmap获得内存是连续的)。Mmap为malloc中满足应用内存请求提供了除brk之外的第二种选 择。
dlmalloc使用系统调用接口 brk和mmap向底层操作系统管理heap空间。Brk系统调用可以改变进程当前heap最高点的指针，使其向上或向下移动(即扩大或减小heap大 小).而使用mmap满足非常大的内存块请求，mmap总是以页面位单位进行内存映射，即使只mmap一个byte也会映射一整个页面，大部分系统页面大 小是4096bytes，有些系统可能更大MiB or 2MiB with on IA-32)。但mmap的优点是一旦释放后能够立刻被操作系统分配给其他进程使用。所以glibc中的doug lea实现的分配器(以下简称dlmalloc)结合使用mmap满足大内存块的请求，brk管理heap满足小内存块请求。

Mmap的使用可以进一步减少内存碎片的产生，因为mmap并不会产生需要管理的holes，但由于mmap的实现和其内部bookkeeping消耗限 制mmap只能在有限的场合下才适合使用，比如：在当前所有的提供mmap的系统中，mmap都必须按页面对齐，也就是说mmap调用将比分配存在的 chunk要慢得多，并且造成更多的内部碎片。

因此，dlmalloc仅仅在两种情况下使用mmap，1。对于应用请求大于指定阀值(默认1MB)时，使用mmap满足应用请求；2。内部chunk无法满足应用需要，并且heap空间通过brk无法扩展的时候，使用mmap。

由于有些操作系统当前并未提供mmap，dlmalloc还针对wilderness chunk超过特定阀值之后，将过多的没有用的wilderness内存返回给操作系统。
caching分割和合并chunk需要时间，有时候分割合并的操作可以避免，有两种优化手段：
缓式合并：

当应用free一个chunk时，分配器并不立即对其与其他相邻的空闲chunk进行合并操作，而是期望不久的将来应用会再次请求同样大小的chunk一边快速满足其请求。
预分配：

不是每次应用请求一个size的chunk才进行分配，而是预先分配多个chunk，这样等下次应用请求该大小的chunk时候就不需要分配操作，直接返回已有的空闲chunk以便满足请求。
对于需要连续大量分配或者释放一定范围 内大小的应用程序，进行caching是很有意义的，而如果应用请求和释放的内存块的大小分布很广泛，没什么规律，进行caching将没什么意义，相反 会造成严重的内存消耗。由于分配器对应用的实用内存规律无从知晓，所以很难确定何时进行分配，是应该将小块合并满足大块请求，还是保留小块以便将来满足同 样大小的请求。老版本的dlmalloc对应用使用内存规律作出了某些假设，实际应用结果表明，caching并没有改善dlmalloc的性能，比如在 C++程序中，可能存在大量的类，而每个class的大小并不相等从而造成了大量范围的size，引起最坏情况的发生导致dlmalloc性能下降。最新 的dlmalloc只针对小块内存才进行caching。
小对象分配 由于dlmalloc默认按8bytes对齐，并且最小分配的内存块大小16bytes，对于那些大量分配指针(4bytes)的应用，将造成无法忍受的内存消耗。关于这个话题，mayers在他的effective C++，以及alex在他的modern C++ Design中有过专门的介绍。

分配大小限制由于dlmalloc内部管理内存块称之为chunk，分配大小的限制依据于chunk的定义。Chunk结构如下：

struct malloc_chunk {

INTERNAL_SIZE_T
prev_size;
/* Size of previous chunk (if free).
*/

INTERNAL_SIZE_T
size;
/* Size in bytes, including overhead. */

  struct malloc_chunk* fd;
/* double links -- used only if free. */

  struct malloc_chunk* bk;

};
由上面讨论所知，INTERNAL_SIZE_T类型记录的就是维护chunk大小信息的类型，默认情况下被定义为size_t，另外即使在64-bit系统上也可以将此类型定义为32-bit从而介绍块头的空间消耗。
最大可分配内存：
最大可以分配的内存块大小依赖于物理内存和操作系统，理论上可以分配size_t(unsigned int)类型能够表示的大小的内存，因此理论上最大值是(size_t)-1，或者由C99标准规定的一个对象能够分配的最大内存大小SIZE_MAX(0x7FFF in C90, 0xFFFF in C99)。
虽然C标准规定了size_t为unsigned int，但有些系统没有遵守将其定义为signed int；另外系统调用brk有的参数也是定义为signed int；在这些系统上将无法满足范围到(size_t)-1的内存块请求。但mmap()不内存signed int的限制问题。
最小可分配内存：
dlmalloc最小可分配内存有以下宏值定义：

/* The smallest possible chunk */

#define MIN_CHUNK_SIZE
(sizeof(struct malloc_chunk))

#define MINSIZE
\

(unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))

由上面定义可以看出最小可分配内存同样和INTERNAL_SIZE_T类型有关系，另外也和指针大小、对齐方式有关系。
       对于指针大小为4bytes，默认情况下头占用4bytes(即INTERNAL_SIZE_T定义为size_t)，MINSIZE将等于16。下表列出了几种典型情况，其他情况下的MINSIZE读者可以自行计算。

指针大小	INTERNAL_SIZE_T大小	对齐方式	MINSIZE
4bytes	4bytes	8bytes	16bytes
8bytes	4bytes	8bytes	24bytes
4bytes	8bytes	8bytes	32bytes

即使对于malloc(0)，dlmalloc也会返回一块MINSIZE的内存给用户。

因为管理内存内存块需要，最大消耗的内存小于等于MINSIZE。但当请求大小超过mmap_threshold，dlmalloc将使用mmap满足请求，这种情况下浪费的最大空间是2*sizeof(size_t)+因mmap为了按页(4096或8192bytes)对齐需要的空间。

对齐方式dlmalloc中对齐相关的代码如下：

#ifndef MALLOC_ALIGNMENT

#define MALLOC_ALIGNMENT
(2 * SIZE_SZ)

#endif

/* The corresponding bit mask value */

#define MALLOC_ALIGN_MASK
(MALLOC_ALIGNMENT - 1)

当size_t为4字节时，dlmalloc默认的对齐方式为8bytes对齐，这默认的对齐方式基本能够使用所有的系统和C编译器，如果有需要可以通过定义MALLOC_ALIGNMENT指定更大宽度的对齐方式，必须为2的次幂。


作者：