c - 了解 glibc malloc 分箱实现
问题描述
最近我一直在研究 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 宏定义的指向 bin 的指针如下:
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 用于已经大小排序的空闲块。但是,我不明白剩余垃圾箱的用途。
我怀疑这背后是有原因的。但是,从源代码来看,这对我来说并不清楚。如果你们中的任何人有一些关于为什么这样做的指示或文档,那将不胜感激!
先感谢您!
解决方案
由于 bin 是双向链表,每个 bin 头包含两个指针,而不是一个:第一个指针指向链表的头部,第二个指针指向链尾。这就是为什么指针的数量是 bin 数量的两倍。(请注意,没有使用 bin 编号 0,因此 bin 的数量是真的NBINS - 1
。)
在双向链表实现中很常见,列表实际上是循环的;标题可以看作是一个链接条目。这避免了在添加元素之前检查 bin 是否存在的必要性。(在一个空的 bin 中,first 和 last 都指向 bin header 本身。)但是,a 中的 forward ( fd
) 和 backward ( bk
) 指针malloc_chunk
不在块的开头。为了将 bin 数组中的指针对视为块条目,需要将指针对的地址反向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 显示允许指针一致的反向偏移量。
推荐阅读
- javascript - ReactJs 不存在授权标头
- reactjs - 带有选项组的 Ant Design Select 不显示没有子项的组
- javascript - React - 控制台警告和错误
- javascript - 当另一个类显示设置为 inline-block 时隐藏一个类!重要
- java - java.lang.NoClassDefFoundError:创建订单号错误;
- floating-point - 为什么非正规浮点值的处理速度较慢?
- javascript - 在 Jquery 页面重定向上预填充 Django 表单
- android - com.google.firebase.database.DatabaseException:无法在显示列表视图中将 java.util.HashMap 类型的值转换为字符串
- javascript - 如何在 ace-editor 中执行用户的代码
- python - 计算熊猫数据框中一列的 6 小时平均值,将值绘制为图形上的文本