来大神Linux Buddy System位图大小问题。

Question

free_area_init_core函数中在申请位图的时候，为何大小是size - 1而不是size？
参见bitmap_size = (size-1) >> (i+4);
以order为0举例，16个页框，mapsize需要 16/2=8个bit/8=1Byte。
for (i = 0; ; i++) {
unsigned long bitmap_size;

        INIT_LIST_HEAD(&zone->free_area[i].free_list);
        if (i == MAX_ORDER-1) {
            zone->free_area[i].map = NULL;
            break;
        }

        /*
         * Page buddy system uses "index >> (i+1)",
         * where "index" is at most "size-1".
         *
         * The extra "+3" is to round down to byte
         * size (8 bits per byte assumption). Thus
         * we get "(size-1) >> (i+4)" as the last byte
         * we can access.
         *
         * The "+1" is because we want to round the
         * byte allocation up rather than down. So
         * we should have had a "+7" before we shifted
         * down by three. Also, we have to add one as
         * we actually _use_ the last bit (it's [0,n]
         * inclusive, not [0,n[).
         *
         * So we actually had +7+1 before we shift
         * down by 3. But (n+8) >> 3 == (n >> 3) + 1
         * (modulo overflows, which we do not have).
         *
         * Finally, we LONG_ALIGN because all bitmap
         * operations are on longs.
         */
        bitmap_size = (size-1) >> (i+4);
        bitmap_size = LONG_ALIGN(bitmap_size+1);

Answer 1

在 free_area_init_core 函数中，计算 bitmap_size 时使用 size - 1 而不是 size 的原因是为了确保位图的大小是合适的。

1、首先，让我们来解释一下这段代码的背景。在 Buddy Memory Allocation 策略中，内存块以 2 的幂次方来划分，也就是 1 个页框、2 个页框、4 个页框、8 个页框等等。这些不同大小的内存块都有对应的位图，用于记录哪些块已经被分配或者空闲。

2、在这段代码中，bitmap_size 的计算是为了确定位图的大小，以字节为单位。对于每个不同大小的内存块，都需要一个相应大小的位图。但为了更加高效地使用位图，位图的大小应该是 2 的幂次方，以便对齐。所以在这里，bitmap_size 的计算使用 (size - 1) >> (i + 4)，其中 size 是块大小（页框数），i 是当前的迭代次数。

3、这里 (size - 1) 的操作是将块大小减去 1，以确保计算的结果比块大小小。然后，>> (i + 4) 是将结果右移 i + 4 位，这实际上是将结果除以 2^(i+4)，也就是以 16 为基数来除以。这样可以将结果向上取到最接近的 2 的幂次方的字节数。

4、以 order 为 0 的情况举例，16 个页框，计算 bitmap_size 的过程如下：

1. (16 - 1) 计算得到 15。
2. 15 >> (0 + 4) 计算得到 0，即 2^0 = 1 字节。

5、因此，bitmap_size 为 1 字节，这是适当的大小来表示 16 个页框的分配状态。

总之，这个计算方式确保了位图的大小是 2 的幂次方的字节数，并且适应于不同大小的内存块。