glibc malloc (aka ptmalloc2)

resource:
http://gee.cs.oswego.edu/dl/html/malloc.html
malloc/malloc.c from http://ftp.gnu.org/gnu/glibc/glibc-2.15.tar.gz

基本结构:

	

	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;

	};

细节：

• 已分配的chunk: `boundary tag'方法来管理内存.

	    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Size of previous chunk, if free                 | |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Size of chunk, in bytes                       |M|P|

	      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             User data starts here...                          .

	      .                                                               .

	      .             (malloc_usable_size() bytes)                      .

	      .                                                               |

	nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Size of chunk                                     |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   "chunk" 由malloc 代码使用, "mem" 是返回给用户的，"nextchunk" 是下一连续的块,
   chunk 总是双字对齐的,所以mem也是双字对齐.

•  未分配的chunk: circular doubly-linked lists

	    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Size of previous chunk                            |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	    `head:' |             Size of chunk, in bytes                   |P|

	      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Forward pointer to next chunk in list             |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Back pointer to previous chunk in list            |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	      |             Unused space (may be 0 bytes long)                .

	      .                                                               .

	      .                                                               |

	nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

	    `foot:' |             Size of chunk, in bytes                     |

	      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

     注意到当前chunk 的`foot'  实际上是代表下一块的`prev_size'.

由于chunk size是双字的倍数, size的最低三比特分别用来表示:
   P (PREV_INUSE) (最低比特):
      1 前一块被分配, 此时pre_size未被使用,从而相当于给前一块,故overhead是1字(而不是2字)
      0 未分配, 此时size的前一字表示前一块的大小
   M (IS_MMAPPED):  由mmap 分配
   NON_MAIN_ARENA: 每thread 都有一个arena linked-list, 第一个是main_arena
      (malloc_state 结构, 详细见代码)

算法主要内部结构：
1. regular bins
An array of free chunks headers, 每个bin是双链表, size-order(small bins 相同
  大小), 先进先出原则(freed chunk 放到最前面, 分配从最后开始)，128个bins:
    64 bins of size       8
    32 bins of size      64
    16 bins of size     512
     8 bins of size    4096
     4 bins of size   32768
     2 bins of size  262144
     1 bin  of size what's left
对于前64 bins, 即size < 512, 每个bin是同大小的块集合, 称之为smallbins;
其余为largebins, 且已排序.
布局：16 - 24 - 32 -..- 512 - 576 - 640 ---

2. unsorted chunks
所有split剩下块，返回块的集合.
在这些块放入regular bins之前malloc会有一次尝试对其分配

3. top
Top-most available chunk. (Wilderness preservation)
如果bins分配失败，从这里分配，否则尝试mmap, 再者通过MORECORE申请内存，
增加top.
see sbrk(2)

4. binmap
加快largebin的索引

5. fastbin
An array of lists 最近被释放小块(MAX_FAST_SIZE）, single-link, LIFO

malloc：
exact-fit, last_remaider chunk, best-fit. (Locality preservation)
malloc -> public_mALLOc -> _int_malloc
1. fastbins if any, returns
2. smallbins if any, returns
3. largebins if has fastchunks, consolidate fastchunks
4. unsorted-bin 寻找exact-fit 或 last_remaider chunk, if any returns
   否则将块放入regular bins(largebins need to be sorted)
5. largebins if any, split or exhaust, and returns
6. best-fit if any, split or exhaust, and returns
7. top if available split and returns
8. if has fastchunks, consolidate, then go to step 4
9. calls sYSMALLOc,

sYSMALLOc:
1. mmap if condition is satisfied, if ok then returns
2. not main_arena, try grow_heap and new_heap, otherwise try mmap if mmap is not tried
3. main_arena, MORECORE, otherwise mmap and do some adjustments and fenceposts.
4. finally, do the allocation.

free:
free -> public_fREe -> _int_free
1. if <fastsize, put into fastbin
2. if mmapped, munmap
3. if not mmapped, consolidate backward/forward, put into the unsorted bin or top
4. if freeing a large space, possibly consolidate fastchunks, sYSTRIm

For other similiar routines, says realloc/mallopt, see the implementations for the
details.