Code pitching: Can garbage collection be extended to the JIT-ed code? Why, how and the resulting runtime design impacts on virtual machines.

INTRODUZIONE E PRIMI IMPATTI

Per gestire la memoria dinamica è opportuno introdurre il concetto di heap. Uno heap è una regione di memoria gestita allocando blocchi di questa e tracciandoli in modo che chi ha richiesto l'allocazione possa poi rilasciarli, in modo trasparente. Uno heap gestito da garbage collection consente a chi ha allocato di rilasciare la memoria semplicemente abbandonando il puntatore a quell'area, ovvero quando il puntatore non è più raggiungibile dal programma (ad esempio, nel momento in cui si esce da uno scope).

codepitch1

Come si individuano gli oggetti “morti”, ovvero quelli non più riferiti all'interno di un programma? L'approccio che si usa è chiamato in generale tracing. Gli oggetti ancora “vivi”si trovano partendo da una serie di zone precise del runtime, che saranno spiegate via via in seguito. Tali riferimenti di partenza sono chiamati root. Una prima area in cui cercare riferimenti è naturalmente lo stack: si individuare sullo stack i puntatori allo heap e così anche all'interno degli oggetti da essi puntati. Infatti, quando è trovato un puntatore, l'area di memoria puntata è essa stessa esaminata per individuare se contenga a sua volta puntatori ad altri oggetti e così via fino all'esaurimento dello heap.

Si localizzano così i blocchi di memoria che sono pronti per il riuso in modo da recuperare e poter riutilizzare nuovamente nello heap le aree da considerarsi libere. Durante la fase di tracing, si usa un approccio mark&sweep: gli oggetti vivi sono marcati e i blocchi di memoria marcati non sono inseriti nelle free list, le strutture dati che mantengono la posizione dei blocchi di memoria in cui è possibile allocare. Un problema di questa tecnica usata isolatamente è che lo heap può risultare a lungo andare molto frammentato, conducendo anche a esaurimento dello stesso.

Si adotta pertanto il meccanismo di copy collection: gli oggetti vivi sono spostati periodicamente in un nuovo heap che è allocato all'occorrenza e il vecchio heap è ripulito. Poiché ogni oggetto presente nello heap è spostato, il vantaggio è che per allocarne uno nuovo è sufficiente che sia allocato all'inizio dello heap liberato, senza usare particolari tecniche per individuare aree di dimensione adeguata alla dimensione del nuovo oggetto. Un ulteriore vantaggio è che, compattando in un nuovo heap, dovrebbe risultare una miglior località della memoria. Lo svantaggio maggiore è quello di dover copiare tutti gli oggetti per intero.

Questo difetto può essere annullato adottando un garbage collector generazionale. Questa tecnica sfrutta il fatto che gli oggetti abbiano differenti “durate di vita” e differenti dimensioni. Si divide pertanto lo heap in diversi heap che ospitino solo oggetti con determinate caratteristiche. Ad esempio, oggetti che superano uno o più cicli di garbage collection, vengono copiati in uno heap di oggetti più vecchi. Generazioni più anziane di heap sono meno frequentemente soggette a garbage collection, in quanto, statisticamente, se un oggetto resiste a uno o due cicli di garbage collection è molto probabile che sia utilizzato ancora durante l'esecuzione del programma.

Il garbage collector è scatenato dall'allocatore nel momento in cui esaurisce lo spazio. Il JIT può emettere chiamate a una funzione in grado di chiamare a sua volta il garbage collector in punti che possono aver dato luogo a una esecuzione temporalmente lunga e quindi a un possibile numero elevato di allocazioni in memoria, ad esempio alla fine di un loop.


SCELTE DI DESIGN

 

Per poter visitare gli oggetti durante la fase di tracing in modo consistente e “safe” per l'applicazione, bisogna che tutti i thread siano sospesi (eccetto naturalmente quello relativo al garbage collector).

Ogni thread è posto quindi in un suo stato safe prima di procedere al tracing.

Si procede poi con un walking sullo stack di ogni thread, in modo da individuare e marcare come vivo ogni riferimento a un oggetto. Durante questa fase bisogna tener presente il possibile collegamento tra aree di memoria che fanno parte dello heap gestito dal garbage collector e quelle che non lo sono, in seguito all'utilizzo di codice unmanaged. Nello stesso modo in cui il codice managed condivide lo stack con codice unmanaged, la memoria del “managed heap” deve essere capace di mantenere i puntatori alla memoria unmanaged e viceversa. E' necessario che oggetti managed riferiti da codice unmanaged non siano oggetto di collection, così da far sì che il codice unmanaged che opera fuori dalle convenzioni della virtual machine sia in grado di accedere alle locazioni di memoria direttamente e senza errori.

Questo tipo di informazione può essere mantenuto in una struttura dati del runtime, ad esempio una tabella, che descriva il tipo dei riferimenti agli oggetti, per sapere in che mondo comportarsi con questi. Seguendo le convenzioni del CLR del .NET, tale tabella è chiamata tabella degli object handles e si può pensare di dividere gli oggetti in due grandi gruppi: STRONG reference e PINNED reference: i primi sono oggetti che possono essere spostati, i secondi no.

La tabella dei metodi è una zona ottimale in cui aggiungere informazioni riguardanti la garbage collection. E' possibile aggiungere flag che facilitino, ad esempio, il tracing, mostrando se l'oggetto in questione ha ad esempio altri puntatori ad altri oggetti al suo interno. Si può mantenere una struttura che facilita questa ricerca di puntatori interni. Tale struttura è riempita nel momento in cui la tabella dei metodi è popolata. E' molto usata per il tracing dello stack quando si incontra ad esempio un array ed è usata per individuare puntatori interni a oggetti fra una generazione e un'altra.

Per marcare gli oggetti, se il layout della memoria lo permette, è possibile usare il puntatore di questi alla tabella dei metodi. Lo spazio naturalmente allocato per questo puntatore è overloaded durante la garbage collection per contenere due flag di un bit ciascuno: uno per marcare l'oggetto come vivo o meno, l'altro per sapere se è pinned o no. Non vi sono problemi nell'esecuzione, perché in questa fase i thread sono sospesi. Alla fine del ciclo di garbage collection è indispensabile che questi bit siano rimessi a zero per una corretta esecuzione o che i booleani siano messi al loro valore di default. Altrimenti per marcare gli oggetti è sufficiente un particolare campo booleano presente in ogni oggetto che indichi se l'oggetto sia vivo.

La fase di sweep pone le aree di memoria relative agli oggetti morti in una free list, usata per l'allocazione di nuovi oggetti. Le free list vanno pensate come relative a ciascuna generazione di heap. Lo sweep si implementa tramite un loop partendo dall'indirizzo base di ogni generazione, aggiungendo blocchi alla free list, finché non si trova un oggetto marcato. Spesso, in programmi la cui esecuzione dura molto, non è sufficiente il solo sweep per riutilizzare lo spazio che non serve più. E' necessaria una fase di compattamento, nel nostro caso di copy collection, in cui gli oggetti sono spostati in un nuovo heap, per evitare una eccessiva frammentazione. Una volta che gli oggetti sono stati copiati, è necessario un procedimento per aggiornare i puntatori che non risultano più consistenti. Si scandiscono di nuovo le root, gli heap e la tabella degli object handles, in modo da aggiornare i puntatori modificati.

Una struttura dati del runtime che aiuta sia nella fase di tracing che in quella di sweep è l'implementazione di una write barrier. E' una struttura dati che consiste in un array di bit che può essere usato per scopi differenti a vari livelli dell'architettura. Nella virtual machine è usata per poter conoscere in che punto dello heap sono posti dei puntatori, per individuarli facilmente nella fase di tracing e per modificarli in quella di copy collection. E' quindi una sorta di mappa di bit per gli heap. Si implementa e si mantiene aggiornata facilmente: il compilatore JIT, nel momento in cui incontra un'operazione che memorizza un puntatore, genera codice per effettuare questa operazione e per aggiornare la write barrier. Nella fase di copy collection è poi possibile accedere direttamente alle locazioni che si sa contenere i puntatori e modificarli, tenendo presente i problemi relativi al codice unmanaged precedentemente detti, senza dover scandire tutto lo heap alla loro ricerca.

codepitch2

Esiste poi un problema ovvio riguardante il fatto di utilizzare puntatori a risorse che non sono managed: ad esempio, una connessione a un database, un socket, un file aperto. Tali risorse devono, cioè, essere esplicitamente rilasciate prima che la memoria relativa agli oggetti che le riferiscono sia sweepata. Si introduce nel runtime un concetto chiamato Finalization, atto a questo scopo. Gli oggetti finalizzabili sono classificati nella tabella degli object handles vista in precedenza come WEAK reference. Quando le STRONG reference a questo tipo di oggetti vengono meno, il reference weak è spostato in una struttura dati, chiamata finalization queue, che continua a tenerlo vivo. Esiste un thread dedicato che chiamerà il metodo di finalization sugli oggetti in questa coda, così da rilasciare la risorsa prima di rilasciare il puntatore e far sì che la memoria sia riutilizzata come nel modo normale. Servono quindi due cicli del garbage collector per eliminare questo tipo di oggetti: nel primo, gli oggetti in questa coda sono marcati per essere oggetto di finalization. Nel frattempo il thread è eseguito; nel secondo, il garbage collector trova gli oggetti morti, in quanto non più riferiti da alcun puntatore.

CODE PITCHING

 

E' possibile estendere la garbage collection anche al codice generato dal compilatore JIT (Just-in-Time). In numerose macchine virtuali, i compilatori JIT sono usati per velocizzare il tempo di esecuzione compilando i metodi in codice nativo specializzato per l’hardware sottostante. Un metodo è compilato prima di essere usato la prima volta. Dopodiché, i metodi compilati sono memorizzati in un'area di memoria chiamata code cache. Questa code cache si può pensare residente in uno heap gestito separatamente da quello usato dalla virtual machine per gli oggetti.

La dimensione di questa cache varia durante l’esecuzione del programma. E’ decisa di default una dimensione di partenza. Quando l’accumularsi di codice di metodi compilati raggiunge questa dimensione, sono possibili due scelte. Nella prima, il runtime incrementa la dimensione della cache consentendo ulteriori compilazioni oltre a quelle già presenti. Nella seconda, innesca il garbage collector, i thread sono sospesi ed è mantenuta la dimensione di default della cache e sono cancellati i metodi compilati che non siano attualmente nello scope del programma. Questo è chiamato meccanismo di code pitching ed è una forma di garbage collection.

Si rivela necessaria la sua implementazione se si vuole progettare una macchina virtuale su dispositivi con risorse di memoria limitate, come telefoni cellulari, Pocket PC o altri sistemi embedded. In questi dispositivi, un politica corretta di pitching ha impatti molto importanti sulle prestazioni. Se il pitching è eseguito raramente, la cache del codice può occupare molta memoria. Se il pitching è eseguito troppo frequentemente, un gran numero di metodi deve essere ricompilato e l'efficienza diviene carente.

Vediamo come è possibile implementare tale meccanismo e gli accorgimenti che devono essere presi nel runtime.

Come fa il JIT a sapere quando compilare un metodo? Il JIT deve capire quando è la prima volta che si fa la chiamata di un determinato metodo. Una soluzione consiste nell'implementare un meccanismo chiamato back patching. E' un concetto utilizzato anche nella garbage collection e consiste nel tornare sui propri passi e aggiornare un puntatore affinché punti a una nuova informazione aggiornata. Quando un metodo è chiamato la prima volta, la tabella dei metodi contiene il puntatore al codice del metodo che in realtà punta ad uno stub o thunk di codice, ovvero una routine che si incarica di chiamare il JIT affinché compili il metodo in questione. Quando il JIT ha completato la compilazione, il puntatore della tabella dei metodi è aggiornato affinché punti direttamente al codice jittato.



Chiamata allo stub di indirizzo 0003.

Le successive chiamate puntano al codice compilato.

In un runtime che non supporta il code pitching il campo della tabella dei metodi relativo a questo metodo resterebbe costante fino alla fine dell'esecuzione del programma. Essendo presente il code pitching, però, la situazione cambia. La premessa al suo funzionamento è che la macchina virtuale consente di avere metadati nel runtime che rappresentino il nostro codice e che esista un processo, il compilatore JIT, che compili tenendo presente questi metadati. Per cui, non è necessario mantenere sempre tutto il codice in memoria, mentre è necessario mantenere i metadati aggiornati.

Riassumendo, le chiamate di metodo sono fatte indirettamente attraverso l'utilizzo della tabella dei metodi. Se il codice non è stato jittato è presente il puntatore che demanda a un thunk, altrimenti il puntatore riferisce il codice compilato del metodo. Il code pitching si implementa facilmente modificando il puntatore di questa tabella affinché punti di nuovo al thunk in seguito all'eliminazione del codice dalla code cache.


IMPLEMENTARE IL CODE PITCHING E LA SUA POLITICA

 

Si può pensare come facenti parte del runtime due componenti, un Code Unloader e un Resource Monitor. Quest'ultimo inoltra informazione al code unloader: raccoglie dati sulla heap residency ( ovvero il rapporto fra la memoria occupata e quella totale dello heap: alta residency significa che gran parte della memoria è occupata ), sulla frequenza di invocazione del garbage collector e sulla dimensione del codice compilato. Basandosi su questi dati, il code unloader riesce a prevedere costi e benefici relativi alla deallocazione di una certa porzione di codice. E' questo unloader che procederà alle modifiche sulla tabella dei metodi.

Il compilatore può instrumentare la tabella dei metodi contando a priori quante volte un metodo sarà invocato, annotando di conseguenza la tabella dei metodi oppure dando un particolare attributo alla classe che sarà letto al momento del loading. Si può eliminare il codice dei metodi quando sono alla loro ultima invocazione. Se il conteggio non è stato compiuto in modo esatto, esisterà un po' di overhead dovuto al fatto che si ricompila il metodo più volte.

Un'altra tecnica consiste nell'eliminare tutti i metodi che al momento non sono riferiti dallo stack di esecuzione del runtime.

Esiste anche un'ulteriore soluzione, ovvero quella di adottare una politica LRU ( least recently used ): il code pitching è effettuato sui metodi usati meno di recente. E' stato però dimostrato tramite esperimenti pratici che non presenta vantaggi in termini di performance rispetto ad altre tecniche. Si introduce infatti un grosso overhead per mantenere la lista dei metodi LRU tramite puntatori attraverso le tabelle dei metodi che non è ripagato in termini di performance.

Il code pitching può essere scatenato dalla garbage collection. Questo approccio si basa sul fatto che la frequenza di code unloading si dovrebbe adattare al comportamento dinamico delle risorse. Il code pitching dovrebbe essere eseguito più spesso quando la memoria è al limite, meno frequentemente in altri casi per ridurre un inutile overhead. Un misura che è possibile usare nel runtime è la heap residency. Se il sistema è a corto di memoria, la heap residency è alta. A volte ciò può dar luogo a considerazioni erronee: se un programma esegue molte allocazioni all'inizio della sua esecuzione, può risultare in una heap residency alta, ma l'assenza di ulteriori allocazioni fa sì che non ci sarà bisogna di ulteriore memoria nel corso dell'applicazione. Proprio a causa di questo, è conveniente mediare la heap residency con la frequenza di esecuzione del garbage collector. Per far questo, il resource monitor del runtime inoltra dati sui tempi di esecuzione del garbage collector al code unloader cosicché questi ne conosca la frequenza. Ogni tanti cicli di garbage collection è eseguito anche il code pitching.

Esiste una soluzione per cui il code pitching è invocato nel momento in cui la code cache si trova ad essere piena. E' quella adottata nel CLR del .NET Compact Framework. Il codice jittato è inserito in una cache di dimensione fissa. Quando diventa piena o viene aumentata la sua dimensione, si esegue il code pitching. Un vantaggio è che sicuramente la memoria occupata dal codice non può superare un valore massimo predefinito. Il limite è scoprire un valore di default che si adatti bene alla maggiore parte delle situazioni: se è troppo piccolo, l'applicazione soffre di overhead per l'eccessivo numero di unloading/ricompilazioni, se è troppo grande è come se il code pitching non esistesse. Tutta la code cache è ripulita. I vari thread sono analizzati per identificare gli indirizzi di ritorno nel codice jittato. Tali indirizzi sono rediretti a stub che conoscono gli offset all'interno dei metodi per poter continuare correttamente l'esecuzione.

 

REFERENCES

=======================================================

PDF version [ .pdf ] .