伙伴分配算法 - 开始堆地址

Question

我目前正在尝试实现计算机程序设计Vol:1中描述的Buddy Allocator,它利用了给定数据块及其相应伙伴的地址中的重要不变量.计算如下......

BUDDY(X):

X + 2^i if x mod 2^i+1 = 0
X - 2^i if x mod 2^i-1 = 0

Where X is the address of the block; i is the current order

使伙伴系统表现得如此之好的原因在于,这种用于找到伙伴地址的计算可以简单地通过第i个顺序位的翻转来执行(通过用1 << i进行xor'ing).如果给出左块地址,则返回右块.如果给出正确的块,则返回左侧块.

但是,此方法假定堆以地址0开头.如果堆以具有i顺序范围内的位的地址开始,则执行上述计算将不会为您提供其伙伴的正确地址.

因此,简单地说,有没有办法推广这个计算,以便它可以在任何起始堆地址执行？假设有一个最大订单的约束.IE*如果最大订单是18,我们不会尝试执行大于或等于18的任何计算,因此您不需要找到它的伙伴.

对此非常感谢的任何帮助或建议!

Answer 1

哇，铁杆。阅读Knuth的荣誉！

无论如何，我可能会遗漏要点，但是在某个时候，您正在请求（我想）来自操作系统的连续内存块以将伙伴系统应用于该内存。因此，您难道不能只保留起始地址（还是以后需要它free()），并使用该偏移量使您使用的地址看起来是从零开始的吗？即这样的事情：

uint8_t* start_addr = malloc(SIZE_IN_BYTES);

uint8_t* buddy(uint8_t* real_x) {
    uint8_t *x = real_x - start_addr;
    // do buddy bit-flipping on "x"
    return x + start_addr;
}