c-理解glibcmalloc装箱实现

Question

最近我一直在研究glibcmalloc实现的内部。然而，关于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))

具体来说，我的问题如下。为什么在存储箱阵列中保留的存储箱数量大约是原来的两倍？我知道有一个bin是为调用free产生的未排序的块保留的，并且有NBINS数量的bin用于已经大小排序的空闲块。然而，我不明白剩余垃圾箱的用途。

我怀疑这背后有原因。然而，从源代码来看，我并不清楚这一点。如果你们中的任何人有一些关于为什么要这样做的指针或文档，我们将不胜感激！

提前谢谢！

Answer 1

由于bin是双链表，每个bin标头包含两个指针，而不是一个：第一个指针指向列表的头部，第二个指针指向尾部。这就是为什么指针的数量是bin的两倍。(请注意，没有使用仓位编号0，因此仓位的数量实际上是NBINS - 1。(

正如在双链表实现中常见的那样，列表实际上是循环的；标题可以被视为链接条目。这避免了在添加元素之前检查bin是否在的必要性。(在空bin中，bin标头本身的第一个和最后一个点。(然而，malloc_chunk中的前向(fd(和后向(bk(指针不在块的开头。为了将bin数组中的指针对视为块条目，指针对的地址需要反向偏移malloc_chunk中fd指针的偏移量。

图表可能会有所帮助。下面是垃圾箱中有两块的情况：

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

XXXs显示反向偏移，允许指针保持一致。