分箱式内存管理(bins)

概述

用户释放掉的 chunk 不会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用，降低内存分配的开销。
对于空闲的 chunk，ptmalloc 采用分箱式内存管理方式，根据空闲 chunk 的大小和处于的状态将其放在四个不同的 bin 中，这四个空闲 chunk 的容器包括 fast bins，unsorted bin，small bins 和 large bins。

Small bin

ptmalloc使用small bins管理空闲小chunk，每个small bin中的chunk的大小与bin的index有
如下关系：Chunk_size=2 SIZE_SZ index(SIZE_SZ在32位为4B，在64位为8B)
总共提供了62个bin，如下图所示:

small bins 中一共有 62 个循环双向链表，每个链表中存储的 chunk 大小都一致。比如对于 32 位系统来说，下标 2 对应的双向链表中存储的 chunk 大小为均为 16 字节。每个链表都有链表头结点，这样可以方便对于链表内部结点的管理。此外，small bins 中每个 bin 对应的链表采用 FIFO 的规则，所以同一个链表中先被释放的 chunk 会先被分配出去

Large bin

在 SIZE_SZ 为 4B 的平台上，大于等于 512B 的空闲 chunk，或者，在 SIZE_SZ 为 8B 的平台上，大小大于等于 1024B 的空闲 chunk，则被分配到Large bin 中管理。Large bins 一共包括 63 个 bin
每个 bin 中的 chunk 大小不是一个固定公差的等差数列，而是分成 6 组 bin，每组 bin 是一个固定公差的等差数列，每组的 bin 数量依次为 32、16、8、4、2、1，公差依次为 64B、512B、4096B、32768B、262144B 等，如下图所示:

以 SIZE_SZ 为 4B 的平台为例，第一个 large bin 的起始 chunk 大小为 512B，共 32 个 bin，公差为 64B，等差数列满足如下关系：
Chunk_size=512 + 64 index
第二个 large bin 的起始 chunk 大小为第一组 bin 的结束 chunk 大小，满足如下关系：
Chunk_size=512 + 64 32 + 512 * index
以此类推能计算出Large bin所在的位置

unsorted bin

Unsorted bin 可以看作是 small bins 和 large bins 的 cache(缓存),在glibc中注释如下

/*
 Unsorted chunks
 All remainders from chunk splits, as well as all returned chunks,
 are first placed in the "unsorted" bin. They are then placed
 in regular bins after malloc gives them ONE chance to be used before
 binning. So, basically, the unsorted_chunks list acts as a queue,
 with chunks being placed on it in free (and malloc_consolidate),
 and taken off (to be either used or placed in bins) in malloc.
 The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
 does not have to be taken into account in size comparisons.
*/

大概意思为所有chunk被free后都会先加入到unsorted bin中,他们可以等待一次malloc,在malloc时，如果在 unsorted bin 中没有合适的 chunk，就会把 unsorted bin 中的所有 chunk分别加入到所属的 bin 中，然后再在 bin 中分配合适的 chunk,否则就将unsorted bin中存放的chunk分配出去,剩余的再等待下一次malloc(从英文中猜的)。
unsorted bin的NON_MAIN_ARENA位不会被设置,至于为什么不需要被考虑进大小的比较暂时不明白(应该初学也不用明白)。

Top chunk

Top chunk放在unsorted bin里面讲是因为初始情况下，我们可以将 unsorted chunk 作为 top chunk。我们来看看glibc中对top chunk的注释

/*
   Top

    The top-most available chunk (i.e., the one bordering the end of
    available memory) is treated specially. It is never included in
    any bin, is used only if no other chunk is available, and is
    released back to the system if it is very large (see
    M_TRIM_THRESHOLD).  Because top initially
    points to its own bin with initial zero size, thus forcing
    extension on the first malloc request, we avoid having any special
    code in malloc to check whether it even exists yet. But we still
    need to do so when getting memory from system, so we make
    initial_top treat the bin as a legal but unusable chunk during the
    interval between initialization and the first call to
    sysmalloc. (This is somewhat delicate, since it relies on
    the 2 preceding words to be zero during this interval as well.)
 */

/* Conveniently, the unsorted bin can be used as dummy top on first call */
#define initial_top(M) (unsorted_chunks(M))

Top chunk不属于任何的bin,只有当其他的chunk都不满足要求时才会分配出去，当它过大的时候，top chunk就会被返还给系统。
因为Top chunk最初指向自己且size为0，因此在第一次malloc请求时会强制将其扩展，我们避免任何特殊的代码去检查Top chunk是否存在。
但是在我们申请内存的时候，我们仍然需要这么去做。所以我们在初始化和对sysmalloc的第一次调用期间将这块bin视为合法但不可用的块。

Last reminder

在用户使用 malloc 请求分配内存时，ptmalloc2 找到的 chunk 可能并不和申请的内存大小一致，这时候就将分割之后的剩余部分称之为 last remainder chunk ，unsort bin 也会存这一块。top chunk 分割剩下的部分不会作为 last remainder.

Fast bin

Fast bins 主要是用于提高小内存的分配效率，默认情况下，对于 SIZE_SZ 为 4B 的平台，小于 64B 的 chunk 分配请求，对于 SIZE_SZ 为 8B 的平台，小于 128B 的 chunk 分配请求，首先会查找 fast bins 中是否有所需大小的 chunk 存在（精确匹配），如果存在，就直接返回。
Fast bins可以看作是small bins的一部分cache(缓冲)，他只占据small bins中的前七个chunk，同时他可以看作是LIFO的栈，用单向链表储存。
glibc对其注释如下:

/*
 Fastbins
 An array of lists holding recently freed small chunks. Fastbins
 are not doubly linked. It is faster to single-link them, and
 since chunks are never removed from the middles of these lists,
 double linking is not necessary. Also, unlike regular bins, they
 are not even processed in FIFO order (they use faster LIFO) since
 ordering doesn't much matter in the transient contexts in which
 fastbins are normally used.
 Chunks in fastbins keep their inuse bit set, so they cannot
 be consolidated with other free chunks. malloc_consolidate

 releases all chunks in fastbins and consolidates them with
 other free chunks.
*/

值得注意的是，fast bin的inuse bit始终被设置，这保证了其不会与其他空闲的chunk合并。但在malloc_consolidate函数中将会释放所有的fast bin并且
将他们与其他空闲的chunk合并。

总结

至此，glibc早期的堆结构已经介绍完毕，接下来可以着手分析一些简单的堆题了，至于深入的关于堆的研究也将在后面一一补全。