理解 glibc malloc 的分块实现

Question

理解 glibc malloc 的分块实现

7

最近我一直在研究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_at宏来获取指向bins的指针:

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数组中保留的数量大约是两倍？我知道其中一个bin用于未排序的块（由free函数调用导致），并且有NBINS个bin用于已经按大小排序的空闲块。但是，我不理解剩余bin的用途。

我猜测这背后有一定的原因。然而，从源代码中看不出来这一点。如果你们有任何指示或者文档可以解释其原因，那将非常感激！

提前感谢您！

- HeapScholar

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

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

与双向链表实现中常见的一样，该列表有效地是循环的；头部可以被视为链接条目。这避免了在添加一个元素之前检查bin是否存在的必要性。（在空的bin中，第一个和最后一个都指向bin头本身。）然而，在malloc_chunk中，正向(fd)和反向(bk)指针不在chunk的开头。为了将bin数组中的指针对作为chunk条目处理，需要通过malloc_chunk中fd指针的偏移量来反向偏移指针对的地址。

一个图表可能有所帮助。这是bin中有两个chunk时的情况:

     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 显示反向偏移量，可以使指针保持一致。