根据源码，简单分析一下glibc的ptmalloc分配器的实现，主要是明确malloc与free的流程

下面的例子都是基于glibc 2.19的原始实现，在不说明的情况下为64bit。

相关结构

对于glibc管理堆需要的结构也有很多资料详细介绍过了，这里只简单地回顾一下。

chunk (块)

堆内存分配的基本单位，分为malloc chunk, free chunk, top chunk三类，都使用下面的struct表示

1
2
3
4
5
6
7
8
9
10
11
12
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;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

一般来说这些头信息和用户数据都是按规律紧密排列在内存中，通过prev_size和size可以很容易地找到内存中的上一块和下一块的位置

chunk的大小在32位系统下最小16 bytes，对齐8 bytes;64位系统下最小32 bytes，对齐16 bytes

常量

因为对齐的缘故，size的低3位用于记录chunk的一些flag

1
2
3
#define PREV_INUSE 0x1 //上一块是否在使用
#define IS_MMAPPED 0x2 //是否为mmap的内存
#define NON_MAIN_ARENA 0x4 //是否非main_arena

bins

将free之后的chunk链起来进行管理，以便在下次malloc的时候能够再次利用，分为fast bin, small bin, large bin, unsorted bin 4类。除了fast bin是单向链表LIFO外，其余都是双向循环链表且为FIFO。

实现时，bins都是使用chunk的结构来表示的，但是只使用fd,bk这两个成员，空间上也只分配16 bytes，这是glibc的一种hack的做法。

malloc_state

表示一个模块中堆的分配情况，在主线程中的实例是main_arena这个全局变量

malloc流程

malloc的具体过程在_int_malloc中实现，比较复杂

调整大小

将传入malloc的size加上8 bytes的overhead并向16 bytes对齐，如果不足32 bytes则分配32 bytes，之后所有分配用的size都用调整后的。

检查fastbins

如果块大小符合fast bins，则在对应大小的fastbin中寻找是否有合适的chunk，如果有则直接返回。

检查smallbins

如果块大小符合small bins，则在对应大小的smallbin中寻找是否有合适的chunk，如果有则直接返回。

对于fastbins和smallbins来说，每个bin中的chunk大小都是相同的，所以只要对应的bin中有chunk，就能够直接返回恰好符合的块。

consolidate fastbin

如果块大小符合large bins，这时不会直接在对应的bin中寻找因为这时每个bin中的chunk并不是同一大小不能马上找到正好符合的快。此时会调用malloc_consolidate函数进行fastbin chunk的合并，fastbin chunk在free时不会清除下一块的PREV_INUSE，在此函数中将所有fastbins中的chunk取出并清除其下一块PREV_INUSE以及进行相应的合并操作，最后放入unsorted bin。

处理unsorted bin

如果之前没能返回恰好符合的块，则开始处理unsorted bin中的块

这里有一个例外，如果unsorted bin中只有一个chunk且这个chunk是last_remainder，而且大小足够，则优先使用此chunk，分裂后将前一块返回给用户，剩下的一块作为新的last_remainder再次放入unsorted bin.关于last_remainder可以参考最后给出的understanding glibc malloc中的叙述

  1. 逐个迭代unsorted bin中的块，如果发现chunk的大小正好是需要的大小，则迭代过程中止，直接返回此块;否则将此块放入到对应的small bin或者large bin中，这也是整个heap管理中唯一会将chunk放入small bin与large bin中的代码。
  2. 迭代过程直到unsorted bin中没有chunk或超过最大迭代次数(10000)为止。
  3. 随后开始在small bins与large bins中寻找best-fit，即满足需求大小的最小块，如果能够找到，则分裂后将前一块返回给用户，剩下的块放入unsorted bin中。
  4. 如果没能找到，则回到开头，继续迭代过程，直到unsorted bin空为止

使用top chunk

如果之前的操作都没能找到合适的块，将分裂top chunk返回给用户，若top chunk的大小还是不够，再次执行malloc_consolidate函数清除fastbin，若没有fastbin的chunk，只能使用sysmalloc函数借助系统调用拓展空间。

free流程

free的实现主要在_int_free函数中，相对来说简单一点

安全检查

进行一系列的检查，包括内存地址对齐，PREV_INUSE位是否正确等等，能够发现一些破坏与double free的问题，这些检查以后再详述。

fastbin chunk

如果chunk大小满足fastbin，则不取消下一块的PREV_INUSE位，直接放入fastbin中

consolidate

首先检查被free chunk的前一块，如果未使用，则合并这2块，将前一块从其bin中移除(使用unlink宏)

再检查其后一块，如果发现是top chunk，则最后合并到top chunk中，不放入任何bin;如果不是top chunk且未使用，则再合并这2块，将后一块从其bin中移除。

将合并过的大块放入unsorted bin中。

小结

这里只是大概地阐述了一下malloc/free的过程，比较浅显，主要是大致有一个感觉，之后在利用时还会详述有关的过程。

参考资料

Understanding glibc malloc

这里还有一篇译文: 深入理解glibc malloc

GNU Libc Source: malloc.c