algoritmo di allocazione Buddy - A partire Heap Indirizzo

Question

Attualmente sto cercando di implementare il Buddy Allocator descritto nel The Art of Computer Programming Vol: 1, che si avvale di un invariante importante per l'indirizzo di un determinato blocco di dati e la sua corrispondente compagno. Il calcolo è il seguente ...

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 

Ciò che rende il sistema buddy eseguire così bene è che questo calcolo per trovare l'indirizzo del compagno, può essere semplicemente eseguita con un flip del bit di ordine esimo (via xor'ing con 1 < < i). Se viene fornito l'indirizzo dei blocchi di sinistra, questo restituirà il blocco corretto. Se viene dato il blocco giusto, questo restituirà il blocco di sinistra.

Tuttavia, questo metodo presuppone che l'heap inizi con all'indirizzo 0. Se l'heap inizia con indirizzi che hanno bit nell'intervallo di un ordine che ne ha uno, eseguire il calcolo precedente non fornirà l'indirizzo corretto del suo amico

Quindi, semplicemente, c'è un modo per generalizzare questo calcolo in modo che possa essere eseguito in qualsiasi indirizzo di heap iniziale? Supponiamo che ci sia un limite all'ordine massimo. IE * se l'ordine massimo è 18, non tenteremo di eseguire calcoli superiori o uguali a un ordine di 18, quindi non è necessario trovare il suo compagno.

Qualsiasi aiuto o suggerimento verso questo è molto apprezzato!

Answer 1

Woah, hardcore. Complimenti per aver letto Knuth!

Ad ogni modo, potrei mancare il punto, ma ad un certo punto si sta richiedendo (presumo) un blocco contiguo di memoria dal sistema operativo per applicare il sistema di amici a. Quindi non potresti semplicemente mantenere l'indirizzo iniziale (ne hai bisogno per lo free() in seguito) e usare quell'offset per rendere gli indirizzi che usi sembrano a base zero? Ad esempio qualcosa:

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