Zajímali jste se někdy o to, jakým způsobem je organizován GC heap v CLR? Zde je výsledek mého bádání. GC objekty jsou alokovány z vyhrazeného souvislého bloku paměti. Čím jsou objekty starší, tím se nacházejí na vyšších adresách tohoto souvislého bloku paměti. Speciální ukazatel směřuje na místo, kde bude alokován další objekt. Čas od času dojde k úklidu nepoužitých objektů. Tím se uvolní na heapu nový prostor ale zároveň se vytvoří ostrůvky volného prostoru na heapu. Dále, čas od času dojde ke "smrštění" těchto volných ostrůvků (defragmentation). Defragmentace se neprovádí při každém úklidu haldy z výkonnostních důvodů. Objekty, zůstávají uloženy na zásobníku v pořadí, v jakém byly alokovány, a to i po defragmentaci. To zajišťuje dobrou lokalitu dat (v tom smyslu, že data, která spolu souvisí mohou být nahrána do souvislých bloků procesorové cache).

GC halda je organizována do dvou základních částí. Halda pro velké objekty (objekty větší než 85KB) a halda pro malé objekty. Dále je halda organizována to tří generací podle stáří objektu. Všechny objekty začínají svůj životní cyklus v generaci 0. Pokud objekt "přežije" úklidový cyklus (garbage collection) na haldě dojde k přesunutí objektu do vyšší generace. Maximální stáří, a tedy generace objektu je 2. Smyslem generací je frekvence úklidu objektů na GC haldě. Generace 0 je čištěna častěji než generace 1 a ta je zase čištěna častěji než generace 2. Halda pro velké objekty je čištěna společně s úklidem generace 2.

ROTOR kód obsahuje pouze dvě generace. Na základě tohoto kódu si lze udělat obrázek o struktuře haldy pro malé objekty (objekty menší než 85KB):

GC halda je rozdělena do segmentů. Segment je souvislý blok virtuálního adresového prostoru procesu. Velikost tohoto bloku je 16 MB (tato velikost se ovšem liší pro jednotlivé edice CLR (workstation, workstation 64 bit, server, server 64 bit).  Celý souvislý blok paměti pro každý nový segment je prvně pouze rezervován (reserve). Současně je první 4KB stránka z tohoto bloku paměti označena jako "commited". 

Operační systém Windows rozlišuje mezi těmito dvěma operacemi. Rezervovaná paměť (reserved) má pouze formu zápisu do patřičných systémových tabulek daného procesu. Teprve v okamžiku, kdy je paměťový blok označen jako "commited" memory je tato paměť spravována pomocí mechanismu virtuální paměti (pokud znáte pojmy jako page directory entry, page table entry či page direcoty tak máte představu, co mám na mysli).

Jeden ze segmentů je označen jako "prchavý" (emphemeral). Tento "prchavý" segment hostuje všechny objekty z nulté generace. Tak je tomu v kódu ROTOR. V případě "ostré" verze emphemeral segment hostuje jak objekty nulté generace, tak objekty generace 1 jak je vidět na výše uvedeném schématu.

Segment je rozdělen na hlavičku a tělo. Tělo obsahuje vlastní alokované objekty. Hlavička se skládá ze sady ukazatelů, které popisují jednotlivé části těla segmentu. "reserved" ukazuje na poslední platnou adresu segmentu. "reserved" je tedy sentinel, který je v kódu CLR použit pro detekci toho, zda je daný segment zaplněn. "commited" je poslední platná "commited" adresa. Adresy za tímto ukazatelem jsou označeny jako "reserved" a nejsou platné dokud je systém neoznačí jako "commited". "allocated" je za ideálních podmínek poslední adresa obsahující platný objekt. Tato hodnota souvisí s ukazatelem "plan_allocated". V případě, že živé objekty v daném segmentu tvoří souvislý blok (no fragmentation) obsahují ukazatelé "allocated" a "plan_allocated" stejnou hodnotu. Pokud při úklidu segmentu vzniknou mezi živými objekty "díry" volného prostoru, tak "plan_allocated" ukazuje na první volnou "díru". "next" ukazuje na další segment, jak je naznačeno na obrázku.

gc_heap je datová struktura definována v souboru Gcsmpriv.h. Tato struktura obsahuje velké množství ukazatelů, s nichž nejzajímavější je ukazatel na "finalizator" frontu, ukazatel na emphemeral segment a ukazatel na dvě optimalizační tabulky zvané "brick table" a "card table".

Card a brick tabulky tvoří tělo datové struktury card_table_info. Tyto tabulky definují mapu použití GC haldy. Každá struktura card_table_info popisuje daný blok paměti jehož počátek je dán hodnotou pole "lowest_address".

Card Table

Card table je pole DWORD prvků. Každý DWORD mapuje použití 4KB bloku paměti. To znamená, že jeden bit odpovídá 128 byte paměti. Kdykoliv dojde k změně reference na daný objekt, JITter emituje kód, který nastaví patřičný bit v daném DWORD prvku. To je tak vše, co se dá říci k této tabulce.

Brick Table

Card table mapuje použití paměti. "card table" umožňuje GC rychle najít místa v paměti, která se změnila od poslední GC. To je sice fajn, ale GC potřebuje mít nějaký mechanismus překladu mezi lineární adresou a daným bitem v card table. K tomuto účelu slouží brick table. Brick table je opět tvořena 16-bitovými hodnotami. Každá z těchto hodnot pokrývá 2KB z haldy. Pokud je hodnota v dané brick položce větší než nula, pak tato hodnota reprezentuje offset .NET objektu v daném 2KB segmentu. Pokud je tato hodnota záporná, pak tato hodnota udává počet brick položek, o které se je třeba vrátit zpět. Po tomto přesunu bychom se měli nacházet na brick položce s kladnou hodnotu a tedy s offsetem nového objektu. Tento mechanismus pokrývá situace, kdy daný .NET objekt pokrývá paměťový prostor několika 2KB bloků. Graficky jsem se pokusil znázornit tento mechanismus takto:

Červeně je vyznačen daný .NET objekt. Tento objekt je rozprostřen přes několik brick prvků. Počátek daného card prvku odpovídá jistému 4KB bloku paměti. Tento počátek také odpovídá počátku daného brick prvku. Po nalezení brick prvku pro 2KB v něm najdeme hodnotu -2. To znamená vrať se o dva brick bloky zpět. V tomto zpětném brick prvku najdeme kladnou hodnotu, které obsahuje offset počátku .NET objektu.

Optimalizace CLR 2.0

Správa GC paměti prošla v CLR 2.0 třemi zásadními změnami. Obě změny mají za cíl snížit fragmentování paměti. První změnou je tzv. "demotion". Tato situace pomůže tehdy, máme-li v nulté generaci nějaké "pinned" objekty. Pak se může stát, že mezi těmito "pinned" objekty je dost volného prostoru pro alokaci dalších objektů. V .NET 1.x "pinned" objekty přežily GC cyklus a počátek bloku pro generaci 0 byl posunut za poslední "pinned" objekt. To mělo za následek nevyužitý prostor mezi "pinned" objekty. Pokud byly toto objekty "pinned" dostatečně dlouhou dobu, byly postupně přesunuty do ještě vyšší generace spolu s "dírou" uvnitř. Situace byla horší o to více tehdy, pokud se spolu s "promotion" "pinned" objektů do vyšších generací objevily další, nové "pinned" objekty. Výsledkem byla fragmentovaná paměť.

"Demotion" se snaží tomuto procesu zabránit. Pokud je mezi "pinned" objekty v nulté generaci dostatek místa, tak GC neprovede přesun "pinned" objektů do vyšší generace, ale nechá je v původní nulté generaci. A to i přesto, že tyto objekty přežily úklid. Prostor mezi "pinned" objekty je pak použit pro alokaci nových objektů.

Druhým mechanismem snižující fragmentaci paměti je lepší správa segmentů. V předchozích verzích CLR platilo, že pokud nebylo v aktuálním ephemeral segmentu (segment, který hostuje objekty 1 a 0 generace) dostatek místa, byl vytvořen nový ephemeral segment a původní ephemeral segment se stal segmentem hostujícím 2 generaci objektu (první a druhá  generace v aktuální implementaci nikdy nepřesahuje jeden segment). CLR 2.0 se snaží vylepšit správu segmentů tak, že pokud je nutné alokovat nový segment pro generaci 1 a 0, GC se nejdříve pokusí najít existující segment hostující generaci 2, který má dostatek místa (je téměř prázdný). Místo alokace nové paměti se v takovémto případě provede záměna několika ukazatelů.

Posledním mechanismem správy paměti je funkce zvaná recyklace segmentů (VM hoarding). Tato funkce udržuje "stand-by" list uvolněných segmentů. Pokud GC potřebuje alokovat nový segment, zkontroluje nejdříve tento "stand-by" list a pokud je v tomto seznamu nějaký dostupný segment, použije jej. Tato funkce má ošetřit scénář, kdy se aplikace dostane do bodu, kdy dochází k častému vytváření a zároveň uvolňování segmentů. Například pokud aplikace nahrává a uvolňuje mnoho malých assembly.