Assegnazione memoria memoria e lastra

Question

Sono confuso riguardo a heap e free list. Ho alcune domande e ho la mia comprensione di come funziona malloc in C. Per favore correggimi se sbaglio.

• La memoria heap è organizzata come un elenco collegato (elenco libero) di blocchi di dati ?
• C'è una differenza tra memoria heap e lista libera?

mia comprensione di allocazione di memoria (aperto per consolidamento): - Quando chiamiamo malloc, alloca memoria nell'heap, e lo fa scegliendo un blocco di dati di dimensione adatta dalla free list, giusto?

Quando un certo blocco di memoria viene restituito da malloc, viene rimosso dalla lista libera e l'indirizzo fisico di quel blocco di memoria viene aggiornato nella tabella della pagina.

Quando la memoria è liberata utilizzando free(), il blocco di dati viene inserito nuovamente nella lista libera e, possibilmente, per ridurre la frammentazione, congiuntamente al blocco adiacente, e il bit present nella voce della tabella di pagina viene cancellato.

Quindi l'intero heap è una lista libera (elenco collegato di blocchi liberi) + blocchi dati allocati.

È un quadro completo dell'allocazione dello spazio di archiviazione?

EDIT: Da Linux Kernel Development (Robert Love) capitolo sulla gestione della memoria, Slab allocazione

"Un elenco libero contiene un blocco di disposizione, già stanziati, i dati strutture Quando il codice richiede un. nuova istanza di una struttura dati, è in grado di afferrare una delle strutture dall'elenco libero anziché allocare la quantità sufficiente di memoria e configurarlo per la struttura dati. Successivamente, quando la struttura dati non è più necessaria, viene restituito a la lista gratuita invece di dealloca ted. In questo senso, la lista libera agisce come una cache oggetto, memorizzando una tipo usato frequentemente di oggetto."

Free-list è menzionato come 'blocco di disposizione, la struttura dati assegnato'.

• Come è allocato, quando si trova in un free-list?
• E come sta tornando un blocco di memoria di lista libera _ non _ lo stesso di deallocare quel blocco?
• Come è allocazione lastra diverso da allocazione dello storage

Answer 1

malloc() non è realmente legato alla tabella di pagina; assegna gli indirizzi virtuali e il kernel è responsabile di tenere traccia di dove le pagine sono effettivamente memorizzate nella RAM fisica o su disco.

malloc() interagisce con il kernel tramite la chiamata di sistema brk(), che chiede al kernel di allocare più pagine al processo o rilascia le pagine indietro al kernel. Esistono quindi due livelli di allocazione della memoria:

• Il kernel assegna le pagine a un processo, rendendo tali pagine non disponibili per l'utilizzo da parte di altri processi. Dal punto di vista del kernel, le pagine possono essere posizionate ovunque e le loro posizioni sono tracciate dalla tabella delle pagine, ma dal punto di vista del processo, è uno spazio di indirizzamento virtuale contiguo. La "interruzione di programma" manipolata da brk() è il limite tra gli indirizzi che il kernel consente di accedere (poiché corrispondono a pagine allocate) e gli indirizzi che causano un errore di segmentazione se si tenta di accedervi.
• malloc() alloca porzioni di dimensioni variabili del segmento di dati del programma per l'utilizzo da parte del programma. Quando non c'è abbastanza spazio libero all'interno della dimensione corrente del segmento dati, usa brk() per ottenere più pagine dal kernel, aumentando il segmento dei dati. Quando rileva che uno spazio alla fine del segmento dati non è utilizzato, utilizza brk() per restituire le pagine non utilizzate al kernel, riducendo il segmento dei dati.

Si noti che le pagine possono essere allocate a un processo (dal kernel) anche se il programma in esecuzione in tale processo non sta effettivamente utilizzando le pagine per nulla. Se si imposta free() un blocco di memoria che si trova nel mezzo del segmento di dati, l'implementazione di free() non può utilizzare brk() per ridurre il segmento di dati perché ci sono ancora altri blocchi allocati agli indirizzi più alti. Quindi le pagine rimangono allocate al tuo programma dal punto di vista del kernel, anche se sono "spazio libero" dal punto di vista malloc().

La tua descrizione di come funziona una lista libera mi sembra giusta, anche se non sono esperto nel modo in cui gli allocatori di memoria sono implementati. Ma la citazione che hai postato da Robert Love sembra parlare di allocazione di memoria all'interno del kernel di Linux, che non è correlato all'allocazione di memoria entro il malloc() all'interno di un processo userspace. Quel tipo di lista libera probabilmente funziona in modo diverso.

Answer 2

La prima cosa che si vuole fare è distinguere tra l'allocazione del kernel e del programma. Proprio come ha detto @Wyzard, malloc usa brk (sbrk e qualche volta mmap) per ottenere più pagine dal kernel. La mia comprensione di malloc non è molto buona, ma tiene traccia di ciò che potresti chiamare un'arena. Media l'accesso alla memoria e farà le chiamate di sistema appropriate per allocare la memoria, se necessario.

Una lista libera è un modo per gestire la memoria. Chiamare mmap o brk ogni volta che è necessario più memoria dal kernel è lento e inefficiente. Entrambe richiedono uno switch di contesto in modalità kernel e allocheranno strutture dati per tenere traccia di quale processo possiede memoria. Un elenco libero a livello di utente è un'ottimizzazione per non chiedere e restituire costantemente memoria al kernel. L'obiettivo di un programma utente è di fare il suo lavoro, non aspettare che il kernel faccia il suo lavoro.

Ora per rispondere alle vostre domande:

• Come è allocata, quando si trova in un free-list?

Un altro modo di pensare a una lista libera è come una cache. Un programma farà richieste e il kernel cercherà di soddisfarle on-demand piuttosto che tutte in una volta. Tuttavia, quando un programma è fatto con un pezzo di memoria, il percorso veloce non è quello di restituirlo al kernel, ma metterlo da qualche parte in modo sicuro per essere nuovamente assegnato.In particolare, una lista libera può tracciare le regioni di memoria da cui può prelevare un allocatore, ma farlo in questo modo (con protezione della memoria) che il codice utente non può semplicemente cooptarlo e iniziare a scriverle su tutto .

• E come sta tornando un blocco di memoria di lista libera non la stessa di deallocando quel blocco?

Se assumiamo che veramente deallocazione un blocco è necessario restituire il al kernel e averlo modificare le sue tabelle di pagina interne, quindi la differenza sta veramente in ciò ha il controllo della pagina fisica sottostante (o telaio). In realtà deallocare e restituire la memoria al kernel significa che ora il kernel può prelevare da queste pagine, mentre restituirlo a un utente a livello di lista libera significa che una parte del programma controlla ancora quella memoria.

• In che modo l'allocazione lastra è diversa dall'allocazione dello spazio di archiviazione?

Questo sta iniziando a ottenere un'area diversa (che non mi è molto familiare). L'allocatore di slab è il modo in cui il kernel gestisce l'allocazione della memoria. Da quello che ho visto, la lastra tenta di raggruppare le allocazioni in diverse dimensioni e ha un pool di pagine per soddisfare tali richieste. Credo che le architetture x86 comuni consentiranno allocazioni di memoria fisica continua in potenze di due da 16 byte a 4 MB (sebbene io sia su una macchina a 64 bit). Credo che ci sia un concetto di una lista libera a questo livello, così come i modi per aggiornare o ridimensionare le dimensioni di allocazione in modo efficiente per consentire diverse esigenze di sistema.

D'altra parte, l'allocazione di memoria suona come assicurarsi che ci sia spazio sul disco rigido. In realtà non ho sentito il termine quindi posso solo speculare.

Answer 3

Qui si fa riferimento a due ripartitori differenti,

1. sistema buddy allocatore, utilizzata per attribuire le pagine alla zona, usa il free_list per memorizzare pagine libere, li destinare, dopo aver liberato, se possibile combinarli di nuovo a una dimensione di pagina contigua più grande di ordine superiore.
2. Assegnatore di lastre che funziona su strutture dati già allocate come keme_cache, kmalloc.

fare riferimento a Heap Memory in C Programming per heap.

Per un programma c nello spazio utente, abbiamo memoria heap nel call_stack in cui avviene il malloc. Questo è contrassegnato da _break che è avanzato da sbrk() quando è necessaria più memoria.

Nel kernel di Linux ogni processo ha task_struct che ha il proprio stack e puntatore all'elenco di pagine utilizzate da esso.