Glibc内存管理--ptmalloc2源代码分析（十四）

.2.2  Large bins

在 SIZE_SZ 为 4B 的平台上，大于等于 512B 的空闲 chunk ，或者，在 SIZE_SZ 为 8B 的平台上，大小大于等于 1024B 的空闲 chunk ，由 sorted bins 管理。 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

同理，我们可计算出每个 bin 的起始 chunk 大小和结束 chunk 大小。这些 bin 都是很有规律的，其实 small bins 也是满足类似规律， small bins 可以看着是公差为 8 的等差数列，一共有 64 个 bin （第 0 和 1bin 不存在），所以我们可以将 small bins 和 large bins 存放在同一个包含 128 个 chunk 的数组上，数组的前一部分位 small bins ，后一部分为 large bins ，每个 bin 的 index 为 chunk 数组的下标，于是，我们可以根据数组下标计算出该 bin 的 chunk 大小（ small bins ）或是 chunk 大小范围（ large bins ），也可以根据需要分配内存块大小计算出所需 chunk 所属 bin 的 index ， ptmalloc 使用了一组宏巧妙的实现了这种计算。

#define NBINS             128
#define NSMALLBINS         64
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define MIN_LARGE_SIZE    (NSMALLBINS * SMALLBIN_WIDTH)

#define in_smallbin_range(sz)  \
  ((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE)

#define smallbin_index(sz) \
  (SMALLBIN_WIDTH == 16 ? (((unsigned)(sz)) >> 4) : (((unsigned)(sz)) >> 3))

#define largebin_index_32(sz)                                                \
(((((unsigned long)(sz)) >>  6) <= 38)?  56 + (((unsigned long)(sz)) >>  6): \
 ((((unsigned long)(sz)) >>  9) <= 20)?  91 + (((unsigned long)(sz)) >>  9): \
 ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
 ((((unsigned long)(sz)) >> 15) <=  4)? 119 + (((unsigned long)(sz)) >> 15): \
 ((((unsigned long)(sz)) >> 18) <=  2)? 124 + (((unsigned long)(sz)) >> 18): \
                                        126)

// XXX It remains to be seen whether it is good to keep the widths of
// XXX the buckets the same or whether it should be scaled by a factor
// XXX of two as well.
#define largebin_index_64(sz)                                                \
(((((unsigned long)(sz)) >>  6) <= 48)?  48 + (((unsigned long)(sz)) >>  6): \
 ((((unsigned long)(sz)) >>  9) <= 20)?  91 + (((unsigned long)(sz)) >>  9): \
 ((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
 ((((unsigned long)(sz)) >> 15) <=  4)? 119 + (((unsigned long)(sz)) >> 15): \
 ((((unsigned long)(sz)) >> 18) <=  2)? 124 + (((unsigned long)(sz)) >> 18): \
                                        126)

#define largebin_index(sz) \
  (SIZE_SZ == 8 ? largebin_index_64 (sz) : largebin_index_32 (sz))

#define bin_index(sz) \
 ((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))

      宏 bin_index(sz) 根据所需内存大小计算出所需 bin 的 index ，如果所需内存大小属于 small bins 的大小范围，调用 smallbin_index(sz) ，否则调用 largebin_index(sz)) 。 smallbin_index(sz) 的计算相当简单，如果 SIZE_SZ 为 4B ，则将 sz 除以 8 ，如果 SIZE_SZ 为 8B ，则将 sz 除以 16 ，也就是除以 small bins 中等差数列的公差。 largebin_index(sz) 的计算相对复杂一些，可以用如下的表格直观的显示 chunk 的大小范围与 bin index 的关系。以 SIZE_SZ 为 4B 的平台为例， chunk 大小与 bin index 的对应关系如下表所示:（博客编辑器太弱，不能全部贴出来）

 

开始( 字节)	结束（字节）	Bin index
0	7	不存在
8	15	不存在
16	23	2
24	31	3
32	39	4
40	47	5
48	55	6
56	63	7
64	71	8
72	79	9
80	87	10
88	95	11
96	103	12
104	111	13
112	119	14
120	127	15
128	135	16
136	143	17
144	151	18
152	159	19
160	167	20
168	175	21
176	183	22
184	191	23
192	199	24
200	207	25
208	215	26
216	223	27
224	231	28
232	239	29
240	247	30
248	255	31
256	263	32

 

    注意：上表是 chunk 大小与 bin index 的对应关系，如果对于用户要分配的内存大小 size ，必须先使用 checked_request2size(req, sz) 计算出 chunk 的大小，再使用 bin_index(sz) 计算出 chunk 所属的 bin index 。

         对于 SIZE_SZ 为 4B 的平台， bin[0] 和 bin[1] 是不存在的，因为最小的 chunk 为 16B ， small bins 一共 62 个， large bins 一共 63 个，加起来一共 125 个 bin 。而 NBINS 定义为 128 ，其实 bin[0] 和 bin[127] 都不存在， bin[1] 为 unsorted bin 的 chunk 链表头。

typedef struct malloc_chunk* mbinptr;

/* addressing -- note that bin_at(0) does not exist */
#define bin_at(m, i) \
  (mbinptr) (((char *) &((m)->bins[((i) - 1) * 2]))                           \
             - offsetof (struct malloc_chunk, fd))

/* analog of ++bin */
#define next_bin(b)  ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1)))

/* Reminders about list directionality within bins */
#define first(b)     ((b)->fd)
#define last(b)      ((b)->bk)

/* Take a chunk off a bin list */
#define unlink(P, BK, FD) {                                            \
  FD = P->fd;                                                          \
  BK = P->bk;                                                          \
  if (__builtin_expect (FD->bk != P || BK->fd != P, 0))                \
    malloc_printerr (check_action, "corrupted double-linked list", P); \
  else {                                                               \
    FD->bk = BK;                                                       \
    BK->fd = FD;                                                       \
    if (!in_smallbin_range (P->size)                                   \
        && __builtin_expect (P->fd_nextsize != NULL, 0)) {             \
      assert (P->fd_nextsize->bk_nextsize == P);                       \
      assert (P->bk_nextsize->fd_nextsize == P);                       \
      if (FD->fd_nextsize == NULL) {                                   \
        if (P->fd_nextsize == P)                                       \
          FD->fd_nextsize = FD->bk_nextsize = FD;                      \
        else {                                                         \
          FD->fd_nextsize = P->fd_nextsize;                            \
          FD->bk_nextsize = P->bk_nextsize;                            \
          P->fd_nextsize->bk_nextsize = FD;                            \
          P->bk_nextsize->fd_nextsize = FD;                            \
        }                                                              \
      } else {                                                         \
        P->fd_nextsize->bk_nextsize = P->bk_nextsize;                  \
        P->bk_nextsize->fd_nextsize = P->fd_nextsize;                  \
      }                                                                \
    }                                                                  \
  }                                                                    \
}

    宏 bin_at(m, i) 通过 bin index 获得 bin 的链表头， chunk 中的 fb 和 bk 用于将空闲 chunk 链入链表中，而对于每个 bin 的链表头，只需要这两个域就可以了， prev_size 和 size 对链表都来说都没有意义，浪费空间， ptmalloc 为了节约这点内存空间，增大 cpu 高速缓存的命中率，在 bins 数组中只为每个 bin 预留了两个指针的内存空间用于存放 bin 的链表头的 fb 和 bk 指针。

         从 bin_at(m, i) 的定义可以看出， bin[0] 不存在，以 SIZE_SZ 为 4B 的平台为例， bin[1] 的前 4B 存储的是指针 fb ，后 4B 存储的是指针 bk ，而 bin_at 返回的是 malloc_chunk 的指针，由于 fb 在 malloc_chunk 的偏移地址为 offsetof (struct malloc_chunk, fd))=8 ，所以用 fb 的地址减去 8 就得到 malloc_chunk 的地址。但切记，对 bin 的链表头的 chunk ，一定不能修改 prev_size 和 size 域，这两个域是与其他 bin 的链表头的 fb 和 bk 内存复用的。

     宏 next_bin(b) 用于获得下一个 bin 的地址，根据前面的分析，我们知道只需要将当前 bin 的地址向后移动两个指针的长度就得到下一个 bin 的链表头地址。

     每个 bin 使用双向循环链表管理空闲 chunk ， bin 的链表头的指针 fb 指向第一个可用的 chunk ，指针 bk 指向最后一个可用的 chunk 。宏 first(b) 用于获得 bin 的第一个可用 chunk ，宏 last(b) 用于获得 bin 的最后一个可用的 chunk ，这两个宏便于遍历 bin ，而跳过 bin 的链表头。

     宏 unlink(P, BK, FD) 用于将 chunk 从所在的空闲链表中取出来，注意 large bins 中的空闲 chunk 可能处于两个双向循环链表中， unlink 时需要从两个链表中都删除。