Buddy Allocation Algorithm - Beginning Heap Address

Question

I am currently trying to implement the Buddy Allocator described in The Art of Computer Programming Vol: 1, which takes advantage of an important invariant in the address of a given block of data and its corresponding buddy. The calculation is as follows...

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

What makes the buddy system perform so well is that this calculation to find the buddy's address, can simply be performed with a flip of the ith order bit (via xor'ing it with 1 << i). If given the left blocks address, this will return the right block. If given the right block, this will return the left block.

However, this method assumes that the heap begins with at address 0. If the heap begins with addresses that have bits within the range of i order that have one, performing the above calculation will not give you the correct address of the its buddy.

Therefore, put simply, is there a way to generalize this computation so that it can be performed at any starting heap address? Assume that there is a bound to the max order. IE* if max order is 18, we are not going to try to perform any computation greater than or equal to an order of 18, so you don't need to find its buddy.

Any help or suggestions toward this a very much appreciated!

Answer 1

Woah, hardcore. Kudos for reading Knuth!

Anyway, I might be missing the point, but at some point you're requesting (I presume) a contiguous chunk of memory from the OS to apply the buddy system to. So couldn't you just keep the starting address around (you need it to free() later anyway), and use that offset to make the addresses you use appear to be zero-based? i.e. something like this:

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;
}