Come gestire correttamente la gestione della memoria tramite mmap?

Sto cercando di scrivere il mio malloc e free implementazione free per motivi di apprendimento, con solo mmap e munmap (dato che brk e sbrk sono obsoleti). Ho letto una buona quantità di documentazione sull’argomento, ma ogni esempio che vedo usa sbrk o non spiega molto bene come gestire grandi zone di memoria mappata.

L’idea di ciò che sto cercando di scrivere è questa: prima mappo una grande zona (cioè 512 pagine); questa zona conterrà tutte le allocazioni comprese tra 1 e 992 byte, con incrementi di 16 byte. Farò lo stesso in seguito con una zona di 4096 pagine per allocazioni più grandi (o mmap direttamente se la dimensione richiesta è più grande di una pagina). Quindi ho bisogno di un modo per archiviare informazioni su ogni pezzo che alloco o libero.

La mia domanda è, come gestisco correttamente queste informazioni?

I miei problemi sono: Se creo un elenco collegato, come posso allocare più spazio per ogni nodo? O ho bisogno di copiarlo nella zona mappata? In tal caso, come posso destreggiarmi tra lo spazio dati e lo spazio riservato? O è meglio usare una matrice di dimensioni statiche? Il problema è che la dimensione della mia zona dipende dalle dimensioni della pagina.

Ci sono diverse possibili implementazioni per un malloc basato su mmap:

Sequenziale (primo adattamento, miglior adattamento).

Idea: usa un elenco collegato con l’ultimo blocco di dimensioni alla dimensione rimanente della pagina.

 struct chunk { size_t size; struct chunk *next; int is_free; } 
  1. Allocare
    1. Iterate la vostra lista per un chunk gratuito adatto (ottimizzabile)
    2. Se non viene trovato nulla, ridimensiona l’ultimo blocco alla dimensione richiesta e crea un blocco libero per le dimensioni rimanenti.
    3. Se raggiungi la fine della pagina, (la size è troppo piccola e next è NULL), semplicemente mmap una nuova pagina (ottimizzabile: genera una pagina personalizzata se la dimensione è anormale …)
  2. Per liberare, ancora più semplice: è sufficiente impostare is_free a 1. Opzionalmente, è ansible controllare se il prossimo blocco è anche gratuito e unire entrambi in un blocco libero più grande (attenzione ai bordi della pagina).

Pro: facile da implementare, banale da capire, semplice da modificare.

Contro: non molto efficiente (iterare l’intero elenco per trovare un blocco?), Ha bisogno di un sacco di ottimizzazione, organizzazione della memoria frenetica

Compagni binari (amo l’aritmetica binaria e la ricorsione)

Idea: utilizza le potenze di 2 come unità di misura:

 struct chunk { size_t size; int is_free; } 

la struttura qui non ha bisogno di un next come vedrai.

Il principio è il seguente:

  • Hai una pagina 4096-byte. cioè (-16 per i metadati) 4080 byte utilizzabili
  • Per allocare un blocco piccolo, basta dividere la pagina in due blocchi da 2048-byte e dividere nuovamente la prima metà in blocchi da 1028-byte … fino a quando non si ottiene uno spazio utilizzabile adatto (minimo a 32-byte (16 utilizzabili)) .
  • Ogni blocco, se non è una pagina intera, ha un amico.
  • Finisci con una struttura ad albero come questa: come questo
  • per accedere al tuo amico, usa uno XOR binario tra il tuo puntatore e la dimensione del tuo blocco.

Implementazione:

  1. Allocazione di un blocco di dimensioni
    1. Ottieni il Block_size = 2^k > size + sizeof(chunk) richiesto Block_size = 2^k > size + sizeof(chunk)
    2. trova lo spazio libero più piccolo nell’albero che si adatti a block_size
    3. Se può ridursi, dividilo in modo ricorsivo.
  2. Liberare un blocco
    1. Impostazione is_free su 1
    2. verifica se il tuo amico è libero (dimensione XOR, non dimenticare di verificare che ha le stesse dimensioni di te)
    3. se lo è, raddoppia la sua taglia. Ricorso.

Pro: estremamente veloce ed efficiente in termini di memoria, pulito.

Contro: Complicato, alcuni casi complicati (bordi di pagina e dimensioni di amici) Necessità di mantenere un elenco delle tue pagine

Benne (ho molto tempo da perdere)

Questo è l’unico metodo dei tre che non ho tentato di implementare da solo, quindi posso solo parlare della Teoria:

 struct bucket { size_t buck_num; //number of data segment size_t buck_size; //size of a data segment void *page; void *freeinfo; } 
  • Hai dall’inizio alcune pagine di piccole dimensioni, ciascuna divisa in blocchi di dimensioni costanti (una pagina da 8 byte, una da 16 byte, una da 32 byte e così via)
  • Le “informazioni sulla libertà” di questi bucket di dati sono memorizzate in bitset (strutture che rappresentano un ampio set di input) all’inizio di ogni pagina o in una zona di memoria separata.

per esempio, per un bucket di 512 byte in una pagina di 4096 byte, il bitset che lo rappresenta sarebbe un bitet a 8 bit, supponendo *freeinfo = 01001000 , questo significherebbe che il secondo e il quinto bucket sono gratuiti.

Pro: di gran lunga il più veloce e più pulito nel lungo periodo, più efficiente su molte piccole allocazioni

Contro: Molto ingombrante da implementare, abbastanza pesante per un piccolo programma, necessità di uno spazio di memoria separato per bitset.

Probabilmente ci sono altri algoritmi e implementazioni, ma questi tre sono i più usati, quindi spero che tu possa ottenere un vantaggio su ciò che vuoi fare da questo.