Redboot专栏

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://redboot.blogbus.com/logs/38352001.html

接上篇

dlmalloc有两个重要的数据结构，一个是 chunk, 另一个是bin。

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;
};
这是malloc_chunk的数据结构，不过要注意，一块malloc_chunk可不是只有这么大。
一块malloc_chunk的大小是8byte的倍数。
举个例子：
如果申请一块4byte的内存，只是实际会分配出16byte。
其中，头8byte存放 prev_size和size，然后是4个byte的内存，最后还有4个byte是为了8byte对其的pad。
如下图：

=================
   prev_size [4byte]
   size         [4byte]
  -------------------
   data        [4byte]
  -------------------
   pad         [4byte]
=================

这样我们可以看到，fd和bk在分配出去的时候并不存在，只是在空闲时可用，构成一个双向链表。
当malloc_chunk被free时，就会插入一个双向链表中，留作以后分配，用得就是fd和bk。

而prev_size和size还有一个用处，就是通过这两个元素，可以找到与当前malloc_chunk块相邻的
的malloc_chunk块。
比如：有指针p指向一个malloc_chunk块： struct malloc_chunk * p = ...
这是通过 (struct malloc_chunk *)((char*)(p) + p->size) 和
(struct malloc_chunk *)((char*)(p) - p->prev_size)
就可以找到相邻内存。
这在合并内存的时候非常有用。

另外，要注意的是 size的最低一位是标记是否被用的状态。
因为malloc_chunk的大小是8byte的倍数。所以，低3位都为零，于是最低一位就当作一个标记位。
标记是否被分配。不过，奇怪的是，这个标记是将相邻前一块是否被用 （PREV_INUSE）而不是当前块。
这点一直让我蛮费解的。

关于chunk，这里一篇文章介绍的蛮详细的，还有些配图，很不错。

www.vtzone.org里面还有挺多介绍dlmalloc和内存管理方面的文章，值得读读。

chunk介绍完，就该介绍bin了。
所谓的bin其实就是一些双向链表，在初始化的时候，申请了128个双向链表。用以存放空闲的malloc_chunk。
这样，就可以快速的寻找的所需要的malloc_chunk。其中，前64个bin存放的是固定尺寸
（16byte-512byte以8byte递增）
的malloc_chunk。之后，有相应的映射算法。这是因为小于512byte的分配更频繁，这样做会有更好的效率。
在分配时，以最小块优先，最佳适合的顺序搜索可用的块。

其中注意两个特殊的bin是top和last_remainder。
top存放的是最新从系统获得到的内存，分配时先在其他链表中寻找，如果都没有才在top上面分配，
如果top的内存也不够分了，就从系统申请新的内存，还是放在top上面供分配。

last_remainder是指上次被切分的malloc_chunk，这大概是根据局部化特性，来提高分配的效率。

这样数据结构就大致介绍这么多，下一篇讲讲处理流程