Questo articolo è destinato a chi ha programmato in C ma non ha mai indagato oltre l'interfaccia della libreria standard del C.
Quando si parla di problema della gestione della memoria si fa riferimento a cose diverse in base al contesto. Ad esempio al livello di sviluppo applicativo il problema della gestione della memoria consiste nel quando chiamare "malloc" e "free". A livello della libreria standard il problema di gestire la memoria consiste nel come implementare "malloc" e "free", cioè di come tener traccia delle regioni in uso dall'applicazione e quelle che sono inutilizzate. A livello di sistema operativo il problema consiste nel come organizzare l'accesso alla memoria fisica dei processi mediante la sua virtualizzazione. In generale con problema della gestione di memoria si intende da quali locazioni di memoria centrale la CPU deve leggere e scrivere per poter eseguire un algoritmo ed ottenerne il risultato.
Un allocatore è un componente software che si occupa di fornire regioni di memoria al resto del sistema software del quale fa parte. Questo potrebbe essere un processo utente o un kernel.
Un allocatore generico è un allocatore che rispetta due condizioni: permette di allocare blocchi di dimensione arbitraria e permette di deallocare i blocchi allocati in qualsiasi momento. Un allocatore che rispetta queste condizioni è considerato il più flessibile possibile. Un allocatore generico è tale quando ha un'interfaccia analoga a quella di "malloc"/"free".
è utile essere capaci di scrivere propri allocatori per fare programmi più performanti, robusti e longevi. Programmi con allocatori scritti ad-hoc sono più performanti perchè più un allocatore conosce il contesto di utilizzo, cioè il tipo di oggetti che deve allocare ed il comportamento delle allocazioni, e più è veloce ed usa meglio la memoria. Permette di creare programmi più robusti perchè gli allocatori generici sono oggetti complicati che in quanto tali possono comportarsi in modi inaspettati, quando spesso sono adeguate soluzioni di gestione della memoria molto più semplici. Permette di creare programmi longevi perchè rende il sistema più autocontenuto, quindi il suo funzionamento è più indipendente rispetto all'ambiente circostante che evolve.
Lo Stack Allocator è un allocatore che funziona talmente bene che esistono istruzioni macchina per gestire la memoria in questo modo. Una regione di memoria gestita come uno stack è sempre divisa in una prima metà in uso dal programma ed una libera. Per tener traccia delle allocazioni, l'allocatore deve solo mantenere l'indirizzo e dimensione della regione di memoria complessiva e il numero di byte utilizzati (il numero di byte liberi è la dimensione totale meno quelli usati). Lo stack comincia vuoto (used=0) ed ogni volta che si vogliono allocare N byte, si prende la regione di N byte dall'inizio della memoria libera incrementando il numero di byte in uso di N, e poi ritornando all'applicazione l'indirizzo di questa regione. Quindi ogni volta che si alloca, la memoria viene scalata dalla regione libera. Per la deallocazione è solo possibile deallocare in ordine inverso di allocazione, perchè in ogni dato momento si deve avere una regione contigua usata ed una libera.
Questo allocatore è estremamente rapido perchè le operazioni di allocazione e deallocazione corrispondono all'incremento e il decremento del contatore di byte usati. Tuttavia ha il forte vincolo del poter deallocare solo l'allocazione più recente. Questo vincolo però risulta poco stringente dato che i programmi spesso seguono questo schema perchè organizzati in funzioni (chiamate innestate di funzioni si risolvono sempre prima delle parenti), infatti ogni programma viene di default con uno stack!
La Circular Queue Allocator gestisce la memoria come se fosse una coda circolare. Analogamente allo Stack Allocator ha una regione contigua utilizzata ed una libera. Quando regioni vengono allocate, come per lo stack, la memoria viene scalata da quella libera. La differenza con lo stack è che le deallocazioni vengono fatte in ordine di allocazione, quindi la prima allocazione è la prima ad essere deallocata. Per gestire questo utilizzo circolare sono necessari due interi oltre a indirizzo e dimensione della regione complessiva di memoria, che rappresentano: posizione della prima allocazione relativamente all'inizio della memoria e numero di byte allocati.
Questa soluzione è meno generica rispetto alle altre ma è ottima per alcuni casi specifici. Un esempio interessante è quello dei text editor che implementano la funzionalità di undo/redo. Immaginiamo di progettare un editor di testo al quale allochiamo 1MB per salvare la storia delle operazioni ed eventualmente tornare indietro. Quando abbiamo fatto così tante operazioni da riempire la memoria possiamo decidere di dimenticare la più vecchia per scrivere la nuova. In tal caso la memoria è gestita come una coda.
L'allocatore lineare è un caso degenere dello stack e della queue, che però funziona sorprendentemente bene. Consiste in uno stack dal quale si alloca la memoria mentre non si dealloca mai. Al più la memoria è deallocata tutta in un solo momento mettendo a zero il numero di byte in uso. è detto allocatore lineare perchè la regione di memoria utilizzata cresce in modo lineare, nel senso che non diminuisce. Secondo me un nome più appropriato è allocatore monotono. Un altro modo col quale è chiamato è "Bump-Pointer Allocator", o semplicemente "Bump Allocator", perchè un'allocazione corrisponde ad un "bump" del puntatore che indica dove si trova la regione libera.
Quindi gli oggetti sono allocati in momenti diversi e deallocati tutti assieme. Questo rende l'allocatore lineare ottimo quando (1) l'algoritmo non può mai saturare la memoria o (2) gli oggetti allocati hanno tutti la stessa lifetime. La condizione (1) è poco interessante perchè se l'algoritmo non può mai raggiungere il limite di memoria allore l'uso di memoria potrebbe essere ridotto. La condizione (2) invece è molto interessante perchè molti casi comuni la rispettano. Ogni volta che stiamo costruendo una struttura composta da più nodi (come un albero) che viene usata e poi deallocata nella sua interezza in un solo momento allora rispettiamo la (2). Un esempio più pratico è quello di un webserver che deve rispondere alle richieste HTTP in modo veloce ed in un tempo breve.
Se il blocco di memoria non può ospitare una nuova allocazione ed è disponibile un allocatore di fallback, allora è possibile allocare un nuovo blocco mediante l'allocatore di fallback e continuare scalando byte allocati da li. è possibile tener traccia dei blocchi aggiuntivi mediante una lista concatenata. Alla fine sarà necessario restituire i blocchi all'allocatore di callback scorrendo la lista di blocchi. Una cosa da notare è che secondo questo criterio un nuovo blocco viene istanziato quando quello vecchio non è capace di ospitare una data allocazione. Questo non significa che il blocco vecchio è completamente utilizzato ma che lo spazio rimanente è inferiore alla dimensione dell'allocazione. Siccome una vuolta allocato l'ultimo blocco non si alloca più dai blocchi precedenti, la regione finale inutilizzata diventa frammentazione. Più l'allocazione che scatena la creazione di un nuovo blocco è grande, maggiore sarà la frammentazione. Questo può diventare problematico quando la dimensione delle allocazioni è comparabile a quella del blocco. Tuttavia è da notare che progettare le strutture dati da allocare in modo da essere composte da tante parti di dimensioni ridotte (come un grafo) fa in modo che la possibile frammentazione sia minima.
Un'altra qualità positiva degli allocatori lineari è che portano ad un uso efficiente della cache perchè tutte le allocazioni sono compatte e le regioni di memoria allocate in successione sono molto correlate.
Un altro vantaggio degli allocatori lineari è il fatto che non si deve fare free per le singole allocazioni. Questo è molto comodo nei contesti in cui si devono allocare e deallocare regioni di memoria in molti punti del codice, come ad esempio farebbe un parser.
Un'alternativa alla configurazione multiblocco si può avere nel caso in cui il programma esegua su un sistema operativo che implementa il meccanismo di over-committing della memoria. Questo vuol dire che quando il processo chiede al sistema operativo N pagine di memoria, il sistema operativo aggiunge le entry per le pagine virtuali richieste nella sua tabella delle pagine, tuttavia a queste pagine non ne associa delle versioni fisiche. Solo quando il programma effettivamente accederà a quelle pagine il sistema operativo si occuperà di trovare delle pagine fisiche e farne il committing. Questa è un'ottimizzazione per i processi che chiedono tanta memoria ma ne usano poca. Se immaginiamo di essere su sistemi del genere, allora possiamo creare uno o più allocatori lineari molto grandi (nell'ordine del GB) ed usarli come se avessero dimensioni illimitate, facendo affidamento sul fatto che il sistema operativo allochi solo la memoria che effettivamente usiamo. Questa soluzione è estremamente semplice ma ha l'ovvio problema di funzionare solo su certi sistemi.
Le Free List non sono esattamente uno schema di allocazione quanto un modo per organizzare dei blocchi di memoria non utilizzati.
La free list consiste nel disporre i blocchi liberi in una lista concatenata mantenendo all'interno di ogni blocco il puntatore al blocco successivo nella lista. Questo è possibile perchè il blocco è inutilizzato quindi è possibile memorizzare un puntatore al suo interno. Questa soluzione richiede che i blocchi abbiano una dimensione minima di un puntatore.
Questa lista può essere gestita come uno stack, quindi nuovi blocchi liberi sono messi in testa allo stack e blocchi da usare vengono rimossi dalla testa dello stack.
I vantaggi delle Free List sono la velocità, il fatto operano in tempo costante e hanno un uso di memoria ottimo perchè sfruttano lo spazio libero per tener traccia di se stesso. Lo svantaggio di questo approccio è che richiede letture e scritture in regioni molto sparse nella memoria, potenzialmente causando dei rallentamenti dovuti a cache miss. Se poi si è in ambienti multithread il costo può aumentare ancora.
Un Pool Allocator è un allocatore che permette di allocare regioni di memoria di una sola dimensione. Assumiamo che la regione che gestisce un allocatore del genere è M, mentre la dimensione di un'allocazione è N. In tal caso la memoria viene divista in M/N parti che vengono inserite in una Free List. Allocazioni e deallocazioni consistono in pop e push sulla free list.
è anche possibile ottenere una Pool estendendo uno Stack. In tal caso la regione di memoria inizialmente viene trattata come uno stack dal quale è possibile allocare solo regioni di dimensione N. Quando una regione è deallocata viene messa in una free list, tuttavia non viene usata finchè lo stack non utilizza l'intera memoria. Quando il contatore dello stack raggiunge la fine, allora si comincia ad allocare facendo pop dalla free list. L'effetto di questo meccanismo è di velocizzare le prime M/N allocazioni (perchè incrementare il contatore dello stack è più veloce che fare un pop dalla free list) e di evitare il costo iniziale di costruire la free list. Tuttavia il costo è la complessità di implementazione che potrebbe non valere il guadagno.
Nel caso in cui si usi una Pool che inizialmente si comporta come uno Stack, potrebbe essere attraente l'idea di permettere l'allocazione di regioni con dimensioni variabili. Questo è possibile in pratica e si tradurrebbe in una Free List di regioni di dimensioni diverse (quindi oltre a mantenere il puntatore i blocchi devono anche mantenere la propria dimensione). A questo punto allocare una regione dopo che la fase di stack si è conclusa non corrisponde più ad un pop dalla free list perchè la regione in testa potrebbe non essere della dimensione giusta. è necessario iterare lungo l'intera lista per cercare un blocco adeguato. Nel caso in cui un blocco della dimensione giusta non sia disponibile, sarebbe necessario prenderne uno più grande e dividerlo in due parti (una allocata ed un'altra che rimane della free list). Se viene implementato questo meccanismo di divisione di blocchi ma non di unione di blocchi liberi tangenti (che ha un suo costo), dopo un certo periodo di utilizzi la regione di memoria dell'allocatore risulterebbe completamente frammentata, cioè c'è memoria libera ma non è possibile allocare nulla perchè divisa in regioni troppo piccole.
Come già accennato nel paragrafo sulle Free List, è possibile che il loro carattere avverso nei confronti della cache risulti problematico. In tal caso si può usare una bitmap al posto della Free List, che consiste nel mantenere una regione di memoria che ha un bit per ciascuna regione allocabile. Il valore del bit di una regione indica se è libera o meno. A questo punto l'allocazione e deallocazione corrisponde all'inversione del valore di un bit, che è un'operazione poco costosa. Inoltre, il vantaggio rispetto alla Free List è che queste operazioni richiedono l'accesso a sempre la stessa memoria indipendentemente dalla regione in considerazione, che quindi è sempre in cache.
Un vantaggio della soluzione con Free List è che nel caso sia disponibile un allocatore di fallback (come può essere malloc), quando la Free List risulta vuota durante un'allocazione, è possibile allocare un nuovo blocco mediante l'allocatore di fallback ed aggiungere le nuove regioni di dimensioni N alla Free List. Il problema di questa soluzione è che una volta allocati blocchi aggiuntivi non è facile capire quando è possibile deallocarli. Oltre ad essere difficile capire quando un blocco sia inutilizzato, un blocco non può essere deallocato finchè c'è anche solo un suo slot in uso. Il comportamento ideale sarebbe quello di non allocare slot di blocchi vuoti se c'è ne sono di displonibili in blocchi già in uso. Le soluzioni sono molte e le loro performance dipendono molto dal contesto di utilizzo, tuttavia alcune idee sono queste:
Gli Slab Allocator sono allocatori generici costruiti su un insieme di Pool Allocator ciascuno con una dimensione di allocazione diversa. Quando l'allocatore deve effettuare un'allocazione, trova la Pool di dimensione più adeguata e le inoltra l'allocazione. Quando deve avvenire la deallocazione, lo Slab Allocator capisce a quale Pool appartiene e le inoltra la deallocazione.
Deallocare significa segnare una regione di memoria come inutilizzata a partire dal suo puntatore. Solitamente in fase di deallocazione la dimensione della regione non è nota a priori e va ricavata, quindi lo Slab Allocator deve implementare un meccanismo per capire a quale Pool inoltrare la deallocazione. Le soluzioni sono molte, ma due immediate sono:
La prima soluzione rende banale la deallocazione ma è suscettibile ad errori nel caso di sovrascrizioni non intenzionali dell'header. La seconda soluzione è più lenta ma non ha problemi di questo genere. Inoltre se ciascuna Pool è formata da un'unica regione contigua di memoria, controllare che un puntatore faccia parte di questa regione non dovrebbe essere un'operazione molto costosa. Considerato che uno Slab Allocator può avere fino a 10 Pool, effettuare questi controlli non ha un grande costo. Naturalmente queste sono solo due soluzioni e potrebbero esserci altre opportunità legate al particolare contesto di utilizzo.
Il problema principale di questo genere di allocatore è che un'allocazione fallisce quando la rispettiva Pool è del tutto utilizzata, anche se tutte le altre Pool sono libere. Se però la dimensione delle Pool è proporzionale alla loro probabilità di allocazione, questo limite è attenuato. In questo senso si può vedere il Buddy Allocator (trattato in seguito) come una miglioria dello Slab Allocator, perchè è capace di muovere regioni tra le varie Pool in base all'esigenza.
Il Buddy Allocator può essere visto in prima approssimazione come uno Slab Allocator che mantiene Pool con allocazioni di dimensioni che raddoppiano di pool in pool. Quando deve avvenire un'allocazione si trova la pool più adeguata e si alloca una regione. Se la pool è vuota, si prende un blocco dalla pool successiva (che mantiene blocchi di dimensione doppia) e lo divide in due ottenendo un blocco per l'allocazione ed uno da inserire nella pool originariamente vuota. Se si cerca di estrarre un elemento da una pool che è vuota ed è vuota anche la pool successiva, allora si sale a quella ancora successive e in generale la prima pool non vuota con blocchi più grandi. Una volta ottenuto un blocco lo si divide in due inserendo una della metà nella lista precedente ed il secondo blocco viene portato alle pool ancora inferiori, fino ad ottenere un blocco della dimensione desiderata. Di contro, quando un blocco viene inserito in una pool si cerca la seconda metà dalla quale quale era stato diviso e se trovata, i due blocchi vengono uniti e portati alla pool superiore ricominciando la ricerca della prossima metà più grande finchè non è più possibile fare merging.
Grazie a quest'operazione di split e merge non è necessario associare ad ogni pool una regione esclusiva di memoria. Tutta la memoria in possesso dall'allocatore è divisa nei blocchi relativi alla pool più grande e questi blocchi sono divisi in base all'esigenza. Per questo motivo quelle che ho chiamato pool sino ad ora sono più propriamente free list.
L'unico vincolo stringente è che le dimensioni dei blocchi di ciascuna Free List siano il doppio della Free List precedente. Tuttavia risulta molto comodo se queste dimensioni sono potenze di 2 in particolari. Questo può introdurre molta frammentazione interna perchè se un'allocazione è di poco troppo grande per una lista, alloca sarà allocato un blocco della lista successiva che corrisponde al doppio della dimensione necessaria.
Personalmente consiglio di usare molto pool e allocatori lineari. Generalmente i componenti dei programmi tendono ad operare su un numero ridotto di strutture che quindi possono avere delle proprie pool di allocazione. Nel caso in cui ci sono programmi che creano molti oggetti di dimensioni variabili (come durante la costruzione di un AST facendo parsing) consiglio gli allocatori lineari. A queste due soluzioni si può accostare un uso di malloc nei casi in cui le allocazioni hanno dimensione non nota a priori (quindi la pool non è adeguata), hanno una lifetime molto più lunga o corta rispetto agli altri oggetti allocati (quindi sprecherebbe spazio con un allocatore lineare) oppure è un valore che deve passare tra due componenti del sistema che usano soluzioni di allocazione diverse. In casi più speciali (ad esempio quelli in cui non si vuole dipendere dalla libreria standard) si può adottare un allocatore generico di terze parti come jemalloc o mimalloc, oppure implementare un buddy allocator con uno slab allocator di front-end che riduce la frammentazione interna.
Gli allocatori per C hanno il vincolo che regioni di memoria allocate non possono essere rilocate in modo trasparente all'applicazione perchè il codice utente potrebbe fare affidamento sul particolare valore del puntatore. In ambienti nei quali questa condizione non è vera come in Java, dove ci sono i puntatori ma non è possibile ispezionarne il loro valore, allora diventa possibile una nuova classe di allocatori che rilocano le regioni per ridurre la frammentazione.