In che modo malloc () viene implementato internamente?

Qualcuno può spiegare come malloc() lavori internamente?

A volte ho fatto un strace program e vedo un sacco di chiamate di sistema sbrk , facendo man sbrk parla del fatto che sia usato in malloc() ma non molto di più.

La chiamata di sistema sbrk sposta il “bordo” del segmento di dati. Ciò significa che muove un confine di un’area in cui un programma può leggere / scrivere dati (lasciandolo crescere o restringersi, sebbene AFAIK no malloc dia veramente dei segmenti di memoria al kernel con quel metodo). A parte questo, c’è anche mmap che è usato per mappare i file in memoria ma è anche usato per allocare memoria (se hai bisogno di allocare memoria condivisa, mmap è come lo fai).

Quindi hai due metodi per ottenere più memoria dal kernel: sbrk e mmap . Ci sono varie strategie su come organizzare la memoria che hai dal kernel.

Un modo ingenuo è dividerlo in zone, spesso chiamate “bucket”, che sono dedicate a determinate dimensioni della struttura. Ad esempio, un’implementazione di malloc potrebbe creare bucket per strutture a 16, 64, 256 e 1024 byte. Se chiedi a malloc di darti memoria di una certa dimensione, arrotonda quel numero fino alla dimensione del bucket successiva e poi ti dà un elemento da quel bucket. Se hai bisogno di un’area più grande, malloc potrebbe usare mmap per allocare direttamente il kernel. Se il bucket di una certa dimensione è vuoto, malloc potrebbe utilizzare sbrk per ottenere più spazio per un nuovo bucket.

Esistono vari progetti di malloc e non esiste un vero e proprio modo di implementare malloc poiché è necessario scendere a compromessi tra velocità, spese generali ed evitare la frammentazione / efficacia dello spazio. Ad esempio, se un bucket esaurisce gli elementi un’implementazione potrebbe ottenere un elemento da un bucket più grande, dividerlo e aggiungerlo al bucket che ha esaurito gli elementi. Questo sarebbe abbastanza efficiente dal punto di vista dello spazio, ma non sarebbe ansible con ogni progetto. Se si ottiene un altro bucket tramite sbrk / mmap che potrebbe essere più veloce e persino più semplice, ma non altrettanto efficiente in termini di spazio. Inoltre, il design deve ovviamente tener conto del fatto che “libero” deve in qualche modo rendere lo spazio disponibile a malloc . Non si limita a distribuire la memoria senza riutilizzarla.

Se sei interessato, il proxy SIP OpenSER / Kamailio ha due implementazioni malloc (hanno bisogno di un proprio perché fanno un uso pesante della memoria condivisa e il sistema malloc non supporta la memoria condivisa). Vedi: https://github.com/OpenSIPS/opensips/tree/master/mem

Quindi potresti anche dare un’occhiata all’implementazione di malloc GNU libc , ma quella è molto complicata, IIRC.

Semplicamente malloc e lavoro libero come questo:

malloc fornisce l’accesso all’heap di un processo. L’heap è un costrutto nella libreria di base C (comunemente libc) che consente agli oggetti di ottenere l’accesso esclusivo ad un po ‘di spazio sull’heap del processo.

Ogni allocazione nell’heap è chiamata cella heap. Questo in genere consiste in un’intestazione che contiene informazioni sulla dimensione della cella e un puntatore alla successiva cella heap. Ciò rende effettivamente un heap un elenco collegato.

Quando si avvia un processo, l’heap contiene una singola cella che contiene tutto lo spazio heap assegnato all’avvio. Questa cella esiste nella lista libera dell’heap.

Quando si chiama malloc, la memoria viene prelevata dalla cella heap grande, che viene restituita da malloc. Il resto è formato in una nuova cella heap che consiste di tutto il resto della memoria.

Quando si libera memoria, la cella heap viene aggiunta alla fine della lista libera dell’heap. I malloc successivi camminano nella lista libera alla ricerca di una cella di dimensioni adeguate.

Come ci si può aspettare, l’heap può essere frammentato e il gestore dell’heap può di volta in volta tentare di unire celle adiacenti.

Quando non vi è memoria rimasta nella lista libera per un’allocazione desiderata, malloc chiama brk o sbrk che sono le chiamate di sistema che richiedono più pagine di memoria dal sistema operativo.

Ora ci sono alcune modifiche per ottimizzare le operazioni di heap.

  • Per allocazioni di memoria di grandi dimensioni (in genere> 512 byte, il gestore di heap può andare direttamente al sistema operativo e allocare una pagina di memoria completa.
  • L’heap può specificare una dimensione minima di allocazione per impedire grandi quantità di frammentazione.
  • L’heap può anche dividersi in contenitori uno per piccole allocazioni e uno per allocazioni più grandi per rendere più veloci le allocazioni più grandi.
  • Esistono anche meccanismi intelligenti per ottimizzare l’allocazione dell’heap multi-thread.

È anche importante rendersi conto che spostare semplicemente il puntatore del break di programma con brk e sbrk realtà non alloca la memoria, ma imposta semplicemente lo spazio degli indirizzi. Su Linux, ad esempio, la memoria sarà “supportata” dalle pagine fisiche reali quando si accede a quell’intervallo di indirizzi, il che si tradurrà in un errore di pagina e alla fine porterà al richiamo del kernel nell’allocatore di pagine per ottenere una pagina di supporto.