[原创]Doug Lea's malloc(dlmalloc) 学习笔记（2）

cucook

dlmalloc的基本思想是最优适配算法，被管理地址空间从头开始按照用户要求的大小依次分配给用户，分配给用户的每一个内存块的前面就是这块内存的控制块（header）。如下图：
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|header |User payload |header |User payload |header |User payload |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

dlmalloc算法有两种内存header，分别对应大小小于256字节的块和大于255字节的内存块。

小块内存的控制块：
struct malloc_chunk {
  size_t               prev_foot;  /* Size of previous chunk (if free).  */
  size_t               head;       /* Size and inuse bits. */
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
};
大块内存的控制块：
struct malloc_tree_chunk {
  /* The first four fields must be compatible with malloc_chunk */
  size_t                    prev_foot;
  size_t                    head;
  struct malloc_tree_chunk* fd;
  struct malloc_tree_chunk* bk;
  struct malloc_tree_chunk* child[2];
  struct malloc_tree_chunk* parent;
  bindex_t                  index;
};
/* double links -- used only if free. */
为了减小内存管理本身消耗的内存，需要尽可能减少head的大小。
在一块内存分配给用户之后，后续的分配操作就不再需要考虑这块内存，用户在使用的内存块的header中只需要保存用于释放内存信息。因此，double links -- used only if free.


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/16402/showart_103696.html