Skip to content

binmap 的作用

复制本地路径 | 在线编辑

binmap 用于快速查找空闲 chunk，避免遍历整个 bins 数组。

binmap 中每一位表示 bins 数组中是否有空闲 chunk，具体映射过程为：

  1. 步骤1：根据申请的chunk大小计算出所在bins数组索引值。
  2. 步骤2：根据bins数组索引值计算出binmap数组索引。
  3. 步骤3：根据binmap数组索引找到binmap数组元素。
  4. 步骤4：通过bins数组索引计算出其在binmap中对应的位。

我比较困惑，虽然 binmap 的功能我明白了，但我不清楚为什么要用到他。比如 malloc(0x20) 的时候，那不就是直接在 fastbin 0x20 大小的链表上去找不就可以了？为什么还要 binmap 呢？

一句话先给你结论

binmap 不是为 fastbin 服务的。
它存在的意义，是为了让 malloc 在 smallbin / largebin 阶段
避免无意义的线性扫描。

如果你只盯着 malloc(0x20)，那确实永远用不上 binmap。

malloc 的“真实决策流程”

我们先把一个真实的 malloc 调度顺序摆在桌面上（glibc 2.24 左右）：

malloc(size):
  1. size → nb (对齐后的 chunk size)

  2. 如果 nb <= fastbin_max
       → 直接查 fastbin[nb]
       → 完全不看 binmap

  3. 否则：
       → 看 unsorted bin
       → 尝试 exact fit / split

  4. 否则：
       → 查 smallbin / largebin
           ↑ 这一步才用 binmap

  5. 否则：
       → top chunk / sysmalloc

binmap 只在第 4 步登场

binmap 的实际作用

fastbin 根本不需要 binmap，但是 smallbin 和 largebin 需要

比如 smallbin，有可能从更大的块中进行分割。如果没有 binmap，算法会是如下，相当糟糕：

for (i = smallbin_index(nb); i < NSMALLBINS; i++) {
    if (!bin[i].empty)
        return bin[i];
}

而 largebin 更糟糕了：不是精确 size，而是一个范围；还要维护排序。

可以用 binmap 快速知道附近那些 bin 的空和非空情况，于是查找逻辑变成：

for (word in binmap) {
    if (word != 0) {
        bit = lowest_set_bit(word);
        bin = corresponding_bin(bit);
        check bin;
    }
}

查找复杂度大大降低。

Comments