Je možné, že jiné systémy/knihovny implementují malloc(2) jinak a že se některé struktury, které zde popisuji, nepatrně liší. Můj malloc je ten z Linuxu :-). Také bych rád zdůraznil, žemalloc není součástí jádra, nýbrž je součástí libc a je programován pomocí jaderných volání brk(2) a mmap(2).
Když spustíte nějaký program, má pro sebe standardně vyhrazeno trochu té paměti pro zásobník – obvykle 1MB – (tam se alokují lokální proměnné) a nějakou tu paměť na heapu, kam jsou bezprostředně po spuštění uloženy všechny globální proměnné. Funkce malloc(2) slouží k alokaci paměti na heapu.
Heap je souvislá paměťová oblast, kterou lze zvětšovat pomocí volání jádra brk(2). Toto volání však není pro naše účely uplně nejvhodnější. Jako parametr má totiž adresu, udávající, kam se má heap roztáhnout, což se nám nehodí. Namísto brk(2) proto použijeme jeho obdobu z libc sbrk(2), které předáváme pouze přírůstek, o kolik se má heap zvětšit.
Úplně nejtriviálnější implementace mallocu by mohla vypadat třeba takto:
void * malloc_easy(int size) { return sbrk(size); }
pokud byste nepotřebovali paměť uvolňovat, je malloc_easy určen právě vám.
Jak to funguje?
Pro názornost si představte paměť následujícím způsobem:
----xxxxxxxxxxxxxx----------------------
^ ^
A B
Znak ‚-‘ označuje adresový prostor, kde zatím není namapována žádná paměť. Pokusí-li se program na toto místo zapsat, dojde k segmentation-fault.
Znak ‚x‘ označuje místo, kde je namapován heap. Bod A označuje začátek heapu a bod B označuje jeho konec. Zajímá-li vás, kde leží bod B, jednoduše se můžete zeptat, zavoláte-li sbrk(2) s parametrem 0.
Chcete-li trochu volné paměti, můžete zavolat sbrk(size). Po tomto volání bude paměť vypadat takto:
----xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx-----
^ ^ ^
A B <----size----> C
sbrk(2) vrací jako návratovou hodnotu adresu vrcholu heapu před jeho nárustem. Program zvětší heap a vrátí ukazatel na oblast, kterou tímto zvětšením získal (bod B). malloc_easy tak vlastně alokuje jeden blok volné paměti za druhým pouhým zvětšováním heapu.
Tento způsob alokace paměti je sice velmi hezký a efektivní, avšak má jednu velkou nevýhodu. Alokované bloky paměti nejdou na přeskáčku uvolňovat.
Začnete-li vymýšlet algoritmus pro optimální alokaci paměti, brzy začnete narážet na množství problémů. Paměť se začne fragmentovat, v heapu vznikne spousta děr (uvolněných bloků). Nastane problém s jejich vyhledáváním a spojováním (jsou-li dva prázdné bloky vedle sebe). Funkce malloc(2) tyto problémy řeší tak, jak nejlépe se to podařilo vymyslet.
Bloky, které při alokaci malloc(2) a uvolňování free(2)vznikají, na sebe těsně přiléhaji a můžeme je rozdělit do dvou skupin. Bloky volné a bloky alokované. Volné bloky nemůžou nikdy ležet dva vedle sebe. V případě, že by k tomu mělo dojít, jsou tyto bloky okamžitě spojeny v jeden!
Chcete-li alokovat paměť, malloc(2) se nejprve podívá, nemá-li někde volný blok. (Jak to udělá, si povíme za chvilku.) Jestliže žádný nenajde, provede alokaci paměti podobně jako malloc_easy. Rozdíl je pouze v tom, že před blok volné paměti předřadí halvičku.
Poznámka: na konci heapu není nikdy volný blok. Jakmile se při volání free zjistí, že se uvolňuje poslední blok na heapu, zavolá se sbrk(-size)!
mallocem alokovaný blok paměti bude vypadat takto:
+===========================================+ | Velikost předchozího bloku - je-li volný | +-----------------------------------------+-+ | Velikost bloku v bytech |F| +-----------------------------------------+-+ <- OUT | | | Přidělená paměť | | | +===========================================+
malloc(2) zavolá sbrk(2) a zvětší heap o „požadovanou paměť“ + „velikost hlavičky“. (velikost této hlavičky je, jak si můžete spočítat na nákresu, sizeof(unsigned int) * 2 = 8bytů). Následně pak zapíše do hlavičky „Velikost bloku v bytech“. Bit F značí, je-li předchozí blok alokovaný, resp. že není volný. Při volání malloc(2) se tento bit nastaví vždy na 1/True. Velikost předchozího bloku se nechá nevyplňená. Jako návratovou hodnotu vrátí malloc(2) ukazatel na přidělenou paměť (v nákresu OUT).
Je nutné si uvědomit, že blok předcházející právě alokovanému bloku nikdy nebude volný. Funkce malloc(2) se snaží co možná nejvíce zamezovat fragmentaci paměti, přiléhající volné bloky okamžitě spojuje, nikdy nemůže dojít k alokaci za volným blokem! malloc(2) může při každém volání klidně do F nastavit 1.
Napište si následující program:
int main(int argc, char **argv)
{
int i[10];
*((int *)(((char *)i)+1)) = 5;
return 0;
}
Jestliže tento program spustíte na PC, nic se nestane a program klidně skončí. Pokud však program spustíte například na Sunu, dočkáte se hlášení „Bus Error“. Je to způsobeno tím, že některé architektury vůbec neumožňují přistupovat na nezarovnané (nedělitelné čtyřmi) adresy. Intel takovou operaci sice umožní, avšak doba přístupu k paměti takovýmto způsobem bude mnohem delší.
Z těchto důvodů malloc(2) alokuje pouze paměť zarovnanou na čtyři byty a tím pádem i její velikost zaokrouhluje tak, aby byla dělitelná čtyřmi. Z toho plyne, že poslední bit velikosti bloku bude pokaždé 0 a můžeme ho tedy s klidným srdcem využít pro označení Volný/Používaný.
Poznámka (1): ve skutečnosti, alokujete-li blok paměti menší než 512 bytů, bude velikost skutečné přidělené paměti zaokrouhlena na nejbližší dělitel osmi, takže je úplně jedno, voláte-li malloc(1), nebo malloc(5), získáte stejnou paměť.
Poznámka (2): Můžete si vyzkoušet napsat: ``printf(„%d\n“, ((int *)malloc(x))[-1]);''. Zjistíte tak velikost mallocem alokované paměti +1. Ta „+1“ je právě onen bit, který označuje předchozí blok jako „ALOKOVANÝ“. Neberte to však jako návod, tohle totiž může udělat opravdu jenom prase! :-)
Při uvolňování paměti se free nejprve podívá do hlavičky a zjistí, není-li náhodou předchozí blok volný – (bit F = 0). Pakliže je, má v hlavičce platnou hodnotu udávající i jeho velikost, free tedy může dohledat jeho hlavičku a změnit jeho velikost tak, aby pohltil ten uvolňovaný – čímž oba bloky spojí.
Dále se podívá, není-li volný následující blok. Protože má každý blok ve své hlavičce udanou svou velikost, může je velmi snadno procházet směrem dolů a přitom zjišťovat pomocí bitu F, je-li i následující blok volný. Je-li tomu tak, pak připojí i ten z druhé strany. Zaručí se tak, že nikdy nezůstanou dva volné bloky vedle sebe, vždycky budou spojeny.
Blok uvolněné paměti vypadá takto:
+===========================================+ | Nemá význam (nebo má, ale nevím, jaký) | +-----------------------------------------+-+ | Velikost bloku v bytech |F| +-----------------------------------------+-+ | Ukazatel na předchozí volný blok | PREV +-------------------------------------------+ | Ukazatel na následující volný blok | NEXT +-------------------------------------------+ | | | Volná paměť (může mít nulovou velikost) | | | +===========================================+
Jakmile se blok uvolní, je nutné si ho patřičným způsobem zapamatovat, aby bylo možné ho při další alokaci znovu přidělit. Všechny volné paměťové bloky se proto neustále udržují v obousměrném cyklickém zřetězeném seznamu. Můžete si všimnout dvou nových položek v hlavičce (PREV a NEXT), které slouží právě k uchování ukazatelů na předchozí a následující blok.
Když potom chce malloc(2) najít volný blok určité velikosti, použije k tomu pole 128 front:
Každý volný blok je uložen, v závislosti na své velikosti, právě v jedné z nich. Prvních 64 front slouží k ukládání bloků o velikosti 8 – 64*8, ted, v první frontě budou bloky o velikosti 16 (i s hlavičkou), v druhé 24, 32 atd. Následující tabulka ukazuje, kolik front o jaké velikosti má malloc(2) k dispozici:
O kolik je větší
Počet front: každý další blok:
------------ -----------------
64 8
32 64
16 512
8 4096
4 32768
2 262144
1 ZBYTEK
Pro alokování příliš velkých bloků (větších než 1MB) tento mechanismus není příliš vhodný. Proto malloc(2) namapuje paměť pomocí volání ``mmap(„/dev/zero“)''. Jak to mmap(2) dělá, to už je věc jádra a snad někdy příště bych se o tom mohl rozepsat.
Co říci závěrem?
Rozhodně nemusíte mít strach volat malloc(2) často. Přidělení paměti je velmi rychlé a fragmentace je při normálním používání téměř neznatelná. Měli byste však mít na paměti, že ke každému alokovanému bloku se přiřazuje hlavička, která je velká 8 bytů, alokujete-li bloky pouze o velikosti 8 bytů, bude výsledná velikost spotřebované paměti dvojnásobná. Dále je taky dobré si uvědomit rozestupy velikostí front (jak ukazuje tabulka) a že se velikost alokované paměti zaokrouhluje na tyto hodnoty.
ČLÁNKY DO MAILU