c - 了解 glibc malloc binning 实现

Question

最近我一直在研究 glibc malloc 实现的内部结构。但是，关于 bin 索引，我似乎无法理解一件事。因此，在 malloc_state 结构中，我们有以下声明，为简洁起见，格式略有不同:

struct malloc_state
{
  /* 
       .
       .
       Some declarations
       .
       .
  */

  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];
  
  /* 
       .
       .
       Some more declarations
       .
       .
  */
};

现在我的问题是关于这个结构中 bins 数组的声明。 bins 数组声明如下:mchunkptr bins[NBINS * 2 - 2];根据我的理解，指向 bin 的指针是使用 bin_at 宏定义的，如下所示:

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))

现在具体来说，我的问题如下。为什么 bins 数组中保留的 bin 数量大约是其两倍？我知道有一个 bin 是为调用 free 产生的未排序块保留的，并且对于已经大小排序的空闲块有 NBINS 数量的 bin。但是，我不明白剩余垃圾箱的用途。
我怀疑这背后是有原因的。但是，从源代码来看，这对我来说并不清楚。如果你们中的任何人有一些指示或文档说明为什么这样做，那将不胜感激!
先感谢您!

Answer 1

由于 bins 是双向链表，每个 bin 头包含两个指针，而不是一个:第一个指针指向链表的头部，第二个指针指向链尾。这就是为什么指针数量是垃圾箱数量的两倍。 (请注意，bin 编号 0 未使用，因此 bin 数量实际上是 NBINS - 1 。)
在双向链表实现中很常见，列表实际上是循环的；标题可以看作是一个链接条目。这避免了在添加元素之前检查 bin 是否存在的必要性。 (在一个空的 bin 中，first 和 last 都指向 bin 头本身。)但是，向前( fd )和向后( bk )指针在 malloc_chunk 中不在块的开头。为了把bin数组中的一对指针当作一个chunk entry，这对指针的地址需要反向偏移fd的偏移量。 malloc_chunk 中的指针.
图表可能会有所帮助。以下是 bin 中两个块的外观:

     Bins Array                Chunk 0                Chunk 1 

+--> XXXXXXXXXX <-\     /--> +--------+ <-\     /--> +--------+ <-----+
|    XXXXXXXXXX    \   /     |  p_sz  |    \   /     |  p_sz  |       |
|    XXXXXXXXXX     \ /      +--------+     \ /      +--------+       |
|    XXXXXXXXXX      X       |   sz   |      X       |   sz   |       |
|    +--------+     / \      +--------+     / \      +--------+       |
|    | [2i-2] | -->/   \     |   fd   | -->/   \     |   fd   | ->+   |
|    +--------+         \    +--------+         \    +--------+   |   |
|    | [2i-1] | -->+     \<- |   bk   |          \<- |   bk   |   |   |
|    +--------+    |         +--------+              +--------+   |   |
|                  |                                              |   |
|                  +----------------------------------------------+---+
|                                                                 |
+<----------------------------------------------------------------+

XXX s 显示允许指针一致的反向偏移量。