linux - musl 库 malloc() 实现如何决定 bin 索引？

Question

在 musl 库 malloc() 实现中，MMAP_THRESHOLD 值为 229376 字节，因此 bin_index(用于查找存储在“mal.bins”中的空闲 block 以供以后请求使用的索引)的范围为 0 到 63。我想增加 MMAP_THRESHOLD到 1GB，我是否需要增加 bin_index 的范围...？

Answer 1

我研究了 musl 库 malloc() 的实现。根据我的两个理解，bin 索引计算为以 2 为底的 log 大小。即当大小用 2 的幂表示时的指数部分。

下面是函数 bin_index() 函数的代码片段。

static int bin_index(size_t x)
{
    x = x / SIZE_ALIGN - 1;
    if (x <= 32) return x;
    if (x > 0x1c00) return 63;
    return ((union { float v; uint32_t r; }){(int)x}.r>>21) - 496;
}

在上面的函数中，在计算bin索引时，首先将大小除以32来计算x，如果x值小于或等于32，则使用bin[0]到bin[32]。但如果 x 大于 32，则通过将 x 转换为 32 位(IEEE 754 标准)浮点表示来计算索引。在 32 位表示中，1 位用作符号位，8 位用于指数，23 位用于尾数。如果您在上面的代码中看到，x 值被右移 21 而不是 23(使用了尾数部分的两个额外位)来找到指数。这背后的原因是将两个对数点转换为四步(线性)然后减去偏差496得到指数(bin index)。

为什么是 496...？当我们使用尾数部分的两个额外位时，指数将为 10 位。因此 10 位指数的偏差值为 -512(对于负数)和 511(对于正数)。即可以用 10 位表示的最大数量。在这种情况下，偏差将为 511，因为所有值都将为正。然后从511中减去15(索引偏移量)，将bin索引从32调整为63。511 - 15 = 496

当 MMAP_THRESHOLD 值为 229376 字节时，bin 索引在对数点之间使用四个线性步长。但是，如果我们将 MMAP_THRESHOLD 增加到 1GB，则可以在 bin_index() 中使用从 0 到 63 的相同 bin 索引，只需稍作修改。您应该用 64 位浮点表示而不是 32 位来表示数字，并且不需要使用两个对数点之间具有四个线性步长的 bin 索引，如下所示

 static int bin_index(size_t x)
    {
        x = x / SIZE_ALIGN - 1;
        if (x <= 32) return x;
        if (x > 0x2000000) return 63;
        return ((union { double v; uint64_t r; }){(int64_t)x}.r>>52) - 996;
    }