Alokace haldy
-=-=-=-=-=-=-=-
"Real programs do not generally behave randomly - they are designed to
solve actual problems."
-- Wilson, Johnstone, Neeley, Boles: Dynamic Storage Allocation:
A Survey and Critical Review
Každý asi zná skupinu funkcí malloc, calloc, realloc a free.
Proto používání zde nebudu rozebírat. Raději se porozhlédnu
po možnostnech jejich implementace.
Jak jsem už říkal, klasická implementace zpravuje data
v souvislé oblasti pod ukazatelem break a sama se stará o jeho
posouvání. Asi největším problémem je fragmentace paměti. Například
pokud program naalokuje 4MB blok, potom 2 bajty a první blok uvolní,
pokud knihovna umístila bloky v paměti ve stejném pořadí,
nemůže ukazatel break vrátit, protože je blokován tím malým blokem
na konci. Vzniká tak fragmentace paměti a stím se musí knihovna
nějak vyrovnat.
Bežně se používají dva základní přístupy. V prvním přístupu
(použitým například v glibc) si knihovna udržuje bloky ve dvou
spojových seznamech pro volné a použité bloky. Pokud se blok
alokuje, knihovna se pokusí najít první dostatečně velký blok
v prvním senzamu a užízně z něho potřebnou část (splitting).
Pokud se blok uvolňuje, knihovna přemístí blok z jednoho seznamu
do druhého a opět jej sloučí s okolními volnými bloky (coalesting).
Problémem této implementace je výběr volného bloku. Je jasné, že
z důvodů rychlosti knihovna musí udržovat nějakou chytřejší datovou
strukturu pro volné bloky, než je seznam. Navíc pokud knihovna
vybírá první dostatečně velký blok, počíná si poměrně hloupě. Je
jasné, že by šlo použít chytřejší metody. Pokud ale program používá
nejmenší větší blok, má tendenci paměť rozfragmentovat do malých
nepoužitelných částí. Pokud naopak používá největší, může jej
znehodnotit pro další alokace. Je tedy poměrně těžké zvolit rozumný
algoritmus. Kupodivu i pro první důvod - alokovat první dostupný je
dobrý důvod. Objekty alokované ve stejný čas budou za sebou. Je ale
i pravděpodobné, že program po zkončení dané činnosti všechny tyto
objekty uvolní. To je důvod proč tento hloupý algoritmus se chová
překvapivě dobře.
Druhá implementace využívá bloky jedině velikosti mocniny dvou.
Paměť rozdělí na stránky. U každé stránky ví, bloky jaké velikosti
obsahuje. Při alokaci tedy napřed velikost zaokrouhlí na nejbližší
mocninu dvou a použije se příslušná stránka. Pokud žádná není,
vytvoří se nová.
Jakkoliv tato implementace zní marnotratně, není to tak strašné.
Pokud jsou bloky dostatečně malé (tato metoda se většinou
používá pouze pro malé bloky), blíží se zaokrouhlení na mocninu
dvou paměti přidané v prvním algoritmu pro zarovnání bloku.
Navíc stránka potřebuje pouze malou hlavičku a bitmapu pro bloky.
Datové struktury jsou mnohem menší. Zaokrouhlování způsobuje to,
že mnohem častěji je díra po jedné alokaci použitelná na jinou.
Jiný důvod mluvící pro tuto metodu je, že objety stejné velikosti
jsou většinou objety stejného typu a používají se ke stejnému účelu.
Je tedy pravděpodobné, že také budou naráz uvolněny. Režije je tedy
v mnoha případech dokonce menší, než u prvního algoritmu. Tento
postup používá například klasická UNIXová knihovna.
Jak vidíte, nejedná se zdaleka o triviální problém.
Každá implementace používá jakousi svoji strategii odvozenou
z programátorských zkušeností jejich autorů a proto se chová lépe
či hůře v různých případech. Neexistuje žádná nejlepší strategie
a na každou je nějaký protipříklad. Tyto problémy jsou velmi pěkně
a podrobně rozebrány ve článku [Wilson1].
Popsané metody se většinou používají pro alokace bloků menších,
než je velikost stránky (4KB). Pro větší bloky knihovny často
používají volání mmap a alokují je uprostřed díry mezi haldou
a zásobníkem. Tento přístup je sice pomalejší (pokaždé vyžaduje
volání OS), ale zabrání se tím probémům při vracení paměti systému.
U těchto bloků tedy problémy s fragmentací odpadají. Zůstává pouze
promrhána paměť mezi koncem bloku a koncem stránky (tedy méně, než
4KB).
V DJGPP je situace ještě komplikovanější. DPMI má poněkud
odlišnější přístup ke správě paměti a alokuje souvislé bloky
ve fyzické ram. Bežně knihovna pro každý dový blok alokuje i nový
blok v DPMI. Tento přístup ale má za následek, že v některých
implementacích, kde je počet bloků omezen, program nemůže naalokovat
celou paměť. Druhá implementace je, že knihovna mění velikost
jednoho bloku. Potom se halda chová skoro stejně jako v UNIXu. Často
ale může dojít k přesuvu bloku v RAM (a tedy překopírování všech
dat) a navíc některé implementace nepovolují naalokovat blok větší,
než je polovina volné paměti.
Mallopt
Pro nastavení parametrů alokačního algoritmu slouží funkce
mallopt. Tato funkce odpovídá standardu SVID/XPG. Umožňuje nastavení
následujících hodnot:
M_TRIM_THRESHOLD určuje minimální velikost horního bloku, která
způsobí posunutí ukazatele break zpět (na konci haldy se používá
malá cache, která má za úkol ušetřit volání sbrk).
M_TOP_PAD určuje množství paměti, která se naalokuje navíc při
pousouvání ukazatele break.
M_MMAP_THRESHOLD minimální velikost bloku, pro který se použíje mmap
místo haldy.
M_MMAP_MAX maximální počet bloků, které se alokují pomocí mmap.
Nastavení na 0 vypne používání mmap úplně.
Mallinfo
Další funkce definována standardem SVID/XPG je mallinfo. Tato
funkce vrátí strukturu mallinfo, která obsahuje mnoho informací
o haldě (kolik bloků je alokováno, kolik paměti, fragmentaci apod.).
Ve verzi glibc, která byla v distribuci RedHat 5.0 ale ze záhadných
důvodů haldu nějakým způsobem rozhodí a další alokace paměti selže.
Alokování zarovnaných bloků
Někdy je potřeba, aby byl blok zarovnán na adresu dělitelnou
nějakým číslem. BSD za tímto účelem přidává funkce memalign
a valloc. U funkce memalign můžete přímo udat na jakou hodnotu se
zarovnává a valloc zarovnává na velikost stránky. V glibc můžete
bloky uvolnit pomocí funkce free. V BSD žádný způsob neexistuje.
Mimochodem těmto funkcím chybí manuálová stránka a najdete je pouze
v texinfo dokumentaci.
GNU extensions
GNU přidává ještě jednu zajímavou funkci-mcheck, která umožňuje
zkontrolovat, jestli je halda vpořádku. Tato funkce si nastaví svoje
náhražky za malloc/realloc/free a kontroluje chyby jako je zápis
za koncem bloku a další. Kontrola se musí zaktivovat před tím,
než cokoliv naalokujete. Jinak funkce neudělá nic. Asi nejjednodušší
metoda, jak toho docílit, je přilinkovat knihovnu mcheck (-lmcheck).
Pro kontrolu paměti ale existují mnohem robusnější prostředky o
kterých si něco řekneme později.
Navíc knihovna umožňuje předefinovat ukazatele __malloc_hook
a další. Ty umožňují nadefinovat vlastní funkce pro malloc/free.
(například verzi, která zkončí v případě, že není paměť apod.)
Relocating allocator
Metodou jak účině zabránit fragmentaci je ponechat zprávci
paměti možnost bloky libovolně přesouvat. Tento způsob asi bude
důvěrně znám programátorům z Macintoshe, kde je tato metoda běžně
používána. Při alokaci paměti nedostanete přímo ukazatel na nový
blok, ale ukazatel na ukazatel (handle) na blok. Správce paměti
má potom možnost tento ukazatel libovolně měnit a pokud program
k přistupu do bloku důsledně používá tento nepřímý odkaz, vše bude
fungovat dobře.
Toto řešení ale má mnohá úskalí. Napsat program tak, aby se
ukazatel mohl změnit kdykoliv je téměř nemožné. Žádné knihovní
funkce jazyka C nejsou navrženy tak, aby pracovaly korektně
v případě, že se blok přesune. Navíc by všechny tyto odkazy musely
být typu volatile a to by vedlo k velmi špatnému výslednému kódu.
Proto se většinou možnost přesouvání bloků musí omezit na nějakou
speciální akci (například volání funkcí pro zprávu paměti)
a proto se tato metoda vpodstatě nedá použít v multithreadovaných
programech, nebo programech co alokují paměť ze signálů.
Z těchto důvodů osobně nevidím žádně větší využití pro takovou
zprávu paměti. Přesto ale glibc implementuje několik funkcí pro
práci s takovými bloky:
void * r_alloc (void **HANDLEPTR, size_t SIZE)
void r_alloc_free (void **HANDLEPTR)
void * r_re_alloc (void **HANDLEPTR, size_t SIZE)
Jejich použití je asi jasné a proto je zde nebudu rozebírat.
Jenom je nutné poznamenat, že handle se musí nacházet v paměti,
která se nebude přesouvat a nemůže být tedy v bloku alokovaném
pomocí r_alloc.
Obstacks
Halda je rozhodně nejuniverzálnějším prostředkem pro alokaci
paměti. Za její univerzálnost se ale platí její marnotratností
a pomalostí. Jeden z nejklasičtějších případů, pro které se nehodí
je načítání neomezeně dlouhých stringů. Vpodstatě se nám nabízí dvě
základní řešení:
1) můžeme volat realloc po každém načteném byte. Toto řešení je
ale velmi pomalé a protože realloc může pokaždé přesunout blok,
v nejhorším případě je k načtení proběhne v kvadratickém čase.
2) teoreticky asi nejelegantnějším způsobem by asy bylo prohlásit
každý znak za objekt a načítat tyto objekty do spojového seznamu.
Nevýhodou tohoto řešení je to, že hlavičky v seznamu spolu
z režijí zprávce haldy by zabíraly několikanásobně víc, než je
vlastní string. Navíc by se potom z načteným stringem velice
špatně pracovalo.
Je jasné, že ani jedno z těchto řešení není správné. První
řešení lze vylepšit tak, že budeme paměť reallokovat po větších
blocích. Tím se načítání výrazně zryhlí, ale nezmění se časová
složitost. Podobně v druhé metodě můžeme do jednoho prvku seznamu
načíst větší množství znaků a vytvořit tak seznam stránek. I toto
řešení má své problémy zejména při náhodném přístupu k načteným
znakům. To sice lze vyřešit adresářem stránek ale výsledné řešení
je už relativně komplikované a běžné knihovní funkce z načteným
stringem nebudou fungovat. Proto většina programátorů stejně raději
použije pole pevné velikosti. Výsledkem jsou pak problémy typu
buffer overflow.
Situace by byla mnohem jednodušší, kdybychom měli k dispozici
zásobník. Znaky by se prostě načetly do zásobníku a nakonec by byly
pěkně za sebou stejně jako u fixního pole. Nevznila by žádná dalši
režije. Problémem je, že klasický zásobník je už použit pro jiné
účely a proto se k němu nedostaneme. Navíc v připadě, že bychom
načítali více stringů zároveň potřebovali bychom i více zásobníků.
Práve o to se stará konstrukce obstack. Ta umožňuje vytvořit
libovolné množství zásobníků obsahující objekty libovolného typu.
Sice nakonec stejně použije haldu, ale už před námi skryje
nepříjemné implementační detaily. Navíc v glibc exitují ekvivalenty
některých funkcí jako printf pracující z obstacky a proto je práce
s nimi relativně příjemná.
Pokud chcete obstacks vyžít, je nutné napřed zásobník vytvořit
a zinicializovat asi následujícím kódem:
#include <obstack.h>
...
static struct obstack myobstack;
...
obstack_init (&myobstack);
Pro práci s obstacky existuje několik funkcí. Ty jsou v případě
GNU C implementovány jako inline funkce. Pokud používáte starší
překladače, které nemají inline funkce, jsou implementovány jako
makra. Proto je nutné dbát na to, aby parametry těchto funkcí neměly
vedlejší efekt.
V případě, že je obstack inicializován, asi budete chtít do něj
něco uložit. Na obstack můžete postupně ukládat objekty libovolné
velikosti. Můžete na něm alokovat bloky podobně, jako pomocí malloc
na haldě:
void * obstack_alloc (struct obstack *OBSTACK-PTR, int SIZE)
A potom opět uvolňovat pomocí obstack_free:
void obstack_free (struct obstack *OBSTACK-PTR, void *OBJECT)
Můžete ale uvolňovat vždy jen blok na konci zásobníku.
Nejzajímavější vlastností je ale načítání objektů, u kterých
nevíte přesně délku. Ty můžete načítat po částech a každou část
"přilepit" pomocí funkce:
void obstack_grow (struct obstack *OBSTACK-PTR, void *DATA, int SIZE)
Když je obstack hotov, zavoláte obstack_finish(obstack).
Uprostřed načítání objektu nemůžete na obstack přidávat jiné
objekty, ani z něj něco mazat. Pro práci z obstacky existuje ještě
několik dalších funkcí (pro přidávání jednoho znaku, superrychlý
růst atd.). Myslím ale, že nemá smysl to zde rozebírat. V texinfo
dokumentaci glibc v sekci "Memory allocation" najdete víc.
Zajímavé je, že s obstackem lze pracovat také jako se souborem
a otevřít jej pomocí funkce open_obstack_stream(&mystream) a dále
používat běžné funkce pro práci se souborem (například i včetně
fseek, nebo fflush). Přímo práci s obstackem podporuje funkce
obstack_printf a některé další bohužel ne příliš zdokumentované
funkce glibc.
Více hald
V předchozích odstavcích jsem vysvětlil výhody více zásobníků.
I použití více hald přinaší často výhody. Ty jsou patrné zejména,
pokud potřebujeme uložit stav programu, což velice často dělají
interpretery lispu a dalších jazyků. Je potom možné vyhradit si
jednu haldy výlučně na objekty onoho jazyka a uložit pouze ji.
Pokud navíc knihovna zaručí, aby se příště halda nahrála na stejnou
adresu, jste vlastně hotovi.
Knihovny pro zprávu více hald se používají velmi podobně, jako
malloc/free pouze s tím rozdílem, že musíte navíc udat identifikátor
haldy, proto jejich použití nebudu více rozebírat. Standardně glibc
tuto vymoženost neimplementuje a proto si musíte sehnat nějakou
další knihovnu. Jednu najdete v programu checker (o kterém se zmíním
později) a další je v programu gdb.
výheň