Porovnání systémů Linux a FreeBSD (3)

Alokace paměti v jádře

Linux i FreeBSD byly navrženy tak, že stránky alokované jádrem jsou neswapovatelné. Struktury jádra zabírají pouze malou část paměti, a proto jejich neswapovatelnost nevadí. Existují i systémy, které mají některé struktury jádra swapovatelné — například AIX nebo Windows NT — nicméně to komplikuje programování v jádře a přináší to s sebou problémy. Proces se může zablokovat kdykoli při přístupu na swapovatelnou paměť, proto je nutné v tomto místě počítat s možným přepnutím procesu. Není tedy možno držet spinlock a přistupovat na swapovatelnou­ paměť.

Základní funkcí systému je operace alokace stránky. Každá fyzická stránka paměti je popsána strukturou struct page na Linuxu a struct vm_page na FreeBSD. Pole těchto struktur je staticky alokováno při startu systému. Jeho velikost je určená podle množství paměti. Požadavky na stránky se v zásadě dělí na dvě skupiny — na blokující a neblokující (též zvané atomické) alokace paměti. Při blokujícím požadavku je možné, že proces se zablokuje a počká, než swapper nějaké stránky odswapuje na disk nebo než uvolní stránky z cache nebo diskových bufferů. Při atomickém požadavku se proces zablokovat nesmí, a pokud dojde paměť, alokační funkce vrátí NULL. Protože systém za běhu používá skoro celou paměť pro uživatelské procesy a jako diskovou cache, je v něm za běhu poměrně málo volných stránek a k selhání atomické alokace může dojít v podstatě kdykoli. Platí obecný princip: při blokující alokaci je garantováno, že proces paměť dostane (na Linuxu se může stát, že blokující alokace vrátí NULL, ale dochází k tomu jen v extrémním případě, kdy jádro zabralo celou paměť; na FreeBSD blokující alokace neselže nikdy, a pokud jádro zabere celou paměť, je zastaveno na panic). Naproti tomu atomická alokace může kdykoli selhat a kód se s tím musí vypořádat bez nějaké ztráty dat nebo narušení funkčnosti. Atomická alokace se používá v přerušení, neboť obslužná rutina přerušení se zablokovat nesmí. Typickým použitím atomické alokace je alokace paměti pro packety přicházející ze sítě. To se dělá v přerušení od ovladače síťové karty a selhání atomické alokace zde nevadí, neboť protokoly vyšších vrstev se se ztrátou packetu musejí umět vypořádat.

K zajištění dobré funkčnosti systému je třeba mít nějaký limit pro atomické alokace. Pokud je množství volných stránek menší než tento limit, je paměť přidělována už jen atomickým alokacím a blokující alokace musejí počkat, než se stránky odswapují a volná paměť stoupne nad limit. Kdyby takový limit neexistoval, mohlo by se například stát, že proces neustále alokující stránky by zablokoval celé síťování, neboť by okamžitě zabral jakoukoli uvolněnou stránku, na obslužnou rutinu přerušení síťové karty by už nezbylo nic a každý packet by byl zahozen.

Buddy alokátor na Linuxu

Na Linuxu slouží k alokaci stránek funkce struct page *alloc_pages(unsigned int gfp_mask, unsigned int order). První parametr je konstanta GFP_xxx nebo maska složená z konstant __GPF_xxx. GPF_ATOMIC určuje, že jde o atomickou alokaci, GFP_KERNEL znamená, že jde o běžnou blokující alokaci. GPF_USER se používá pro alokaci stránek, o které požádají uživatelské procesy — má stejný význam jako GFP_KERNEL až na to, že pokud je zaplněná celá paměť i swap, je limit pro GFP_USER vyšší než pro GPF_KERNEL. Je to proto, aby, když uživatelské procesy spotřebují celou paměť, ještě nějaká paměť zbyla jádru. GPF_NOFS a GPF_NOIO znamená, že alokátor nesmí zavolat filesystém nebo blokový io-systém, aby uvolnil paměť, protože by mohlo dojít k deadlocku (použití těchto dvou příznaků mi nepřipadá moc čisté — alokátor sice nemůže zavolat filesystém nebo io-systém, nicméně může klidně čekat, než swapovací proces kswapd nějakou paměť uvolní — a kswapd volá filesystém i io-systém. Jak uvidíme později, ono je to s těmi deadlocky docela zamotané a ne moc dobře vyřešené). Další příznaky určují, zda paměť musí ležet v dolních 16M paměti, aby byla použitelná pro ISA DMA, nebo zda může ležet v nenamapované high-memory zóně, o které bude řeč později.

Druhý parametr funkce alloc_pages je dvojkový logaritmus počtu stránek, který se má alokovat. Je-li to nula, alokuje se jedna stránka, je-li to 1 či 2, alokují se dvě či čtyři stránky a tak dále. Alokované stránky jsou v jednom souvislém bloku. Linux používá k alokaci buddy alokátor, který drží pro jednotlivé mocniny dvojky seznamy bloků příslušného počtu volných stránek. Je držen seznam všech volných nespárovatelných stránek. Dále je držen seznam všech volných dvojic stránek (dvojice stránek musí být zarovnaná — t.j. dolní stránka má pořadí, které je dělitelné dvěma), pak je držen seznam všech volných čtveřic stránek (dolní stránka čtveřice má pořadí dělitelné čtyřmi) a tak dále i pro vyšší mocniny dvojky. Při požadavku o alokaci určitého počtu stránek se alokátor nejdříve podívá do seznamu odpovídajícího danému počtu. Pokud tam blok stránek nalezne, tak ho přidělí. Pokud ho tam nenalezne, podívá se do dalšího seznamu (obsahujícího bloky dvojnásobné velikosti), a když tam nalezne blok, rozdělí ho na poloviny. Jednu polovinu uloží do nižšího seznamu bloků poloviční délky a druhou polovinu vrátí. Pokud nenalezne blok ani tam, podívá se do dalšího seznamu a tak dále, až narazí na seznam největších bloků. Pokud nenalezne volný blok ani tam, alokace selže. Při uvolnění bloku stránek se kontroluje, zda onen blok nemá volný blok v páru, a pokud ano, oba bloky se spojí a přidají se do vyššího seznamu. Pokud nový spojený blok má opět volný blok v páru, spojí se i tyhle, a tak dále.

Buddy alokátor s sebou přináší problém — a tím je fragmentace paměti. Pokud není spotřebovaná celá paměť, je garantováno, že se podaří alokovat jednu stránku; bohužel už není garantováno, že se podaří alokovat více souvislých stránek. Na starších jádrech 2.4 pla­tilo, že alokace mohla kdykoli selhat, pokud parametr order byl větší než nula. Alokace dvou souvislých stránek je na IA32 potřeba k vytvoření procesu, proto se tam mohlo kdykoli stát, že vytvoření procesu selže a vrátí chybu ENOMEM. V jádře 2.4.18 je to napsáno tak, že pokud je order <= 3 a alokace selže (a nejedná se o atomickou alokaci), bude se v cyklu neustále volat funkce na uvolnění nebo swapování stránek, doufajíc, že se blok potřebné velikosti podaří vytvořit (v dřívějších jádrech tento cyklus probíhal jen pro order == 0). Nepovede to sice k náhodnému selhání vytváření procesu jako dřív, nicméně při velmi nevhodném umístění stránek a nedostatku swapu může dojít k nekonečnému cyklu. Například pokud je alokována polovina paměti a stránky jsou tak nešikovně umístěny, že volné stránky netvoří žádný pár, nepodaří se vytvořit nový proces a tahle operace bude cyklit v nekonečné smyčce. Nicméně pravděpodobnost, že se to stane, je velmi malá. Pokud je navíc dostatek swapovacího místa, budou stránky swapovány tak dlouho, dokud se blok potřebné velikosti nevytvoří.

Barvení stránek na FreeBSD

FreeBSD nemá buddy alokátor. K alokaci jedné stránky se používá funkce struct *vm_page *vm_page_alloc(vm_object_t object, vm_pindex_t index, int page_req). První parametr je objekt, do kterého se má stránka uložit, a druhý je index v tomto objektu (vm_objekty budou popsány později; pro alokaci stránek pro jádro se používá objekt jádra kernel_object). Třetí parametr určuje prioritu alokace —nejnižší pro uživatelský proces, vyšší pro systém, nejvyšší pro interrupt. Tato funkce se nikdy neblokuje. Pokud paměť není nebo pokud je množství volné paměti pod kvótou pro danou prioritu alokace, vrátí NULL. Pokud vrátí NULL, může se kód, který ji volal, zablokovat pomocí makra VM_WAIT; a čekat, než swapper nějaké stránky odswapuje a nějaká paměť bude dostupná. Po probuzení z  VM_WAIT je třeba opět zkusit alokaci pomocí vm_page_alloc.

Při alokaci používá FreeBSD algoritmus barvení stránek. Barvení stránek slouží k optimalizaci použití L2 cache. Pro pochopení algoritmu nejdříve popíši, jakým způsobem cache fungují. Nejmenší jednotka, s jakou cache pracuje, je řádka. Například na Pentiu až Pentiu 3 má řádka velikost 32 bytů, na Pentiu 4 má velikost 64 bytů. Ačkoli se říká, že cache je asociativní paměť, není to pravda. Udělat plně asociativní cache není technicky možné, proto má cache adresy. Dolních 5 nebo 6 bitů v adrese je pozice uvnitř řádky, dalších několik bitů adresy je adresa v cachi. Cache pracuje jako obyčejná paměť — těchto několik bitů se použije jako paměťová adresa a podle ní se v cachi najde příslušné místo, na kterém je uloženo několik řádek (typicky 1, 2 nebo 4 — podle toho se cache nazývá jednocestně, dvoucestně nebo čtyřcestně asociativní). Požadovaná celá adresa se porovná s celými adresami těchto několika řádek, a pokud je jedna z nich shodná, prohlásí se hodnota v cachi za nalezenou. Například Pentium 2 má L1 cache čtyřcestně asociativní o velikosti 16kB s délkou řádky 32B. Znamená to tedy, že dolních 5 bitů adresy je offset uvnitř řádky. Dalších 7 bitů je adresa v cachi (spočteno jako log₂(16kB/32B­/4)). Na jedné adrese v cachi se nacházejí čtyři řádky. U Pentia 2 je L2 cache čtyřcestně asociativní, má velikost 512kB a délku řádky 32B. To znamená, že 5 bitů adresy je offset v řádce a 12 dalších bitů je adresa v cachi.

Cache pracuje s fyzickými adresami. (Existují i architektury — například Sparc64 — kde cache pracuje s virtuálními adresami. Je s tím velké množství problémů, pokud dvě virtuální stránky ukazují na jednu stránku fyzickou.) Pokud je například cache čtyřcestně asociativní a uživatelský program alokuje pět souvislých po sobě jdoucích stránek, může se stát, že stránky náhodou padnou na takové fyzické adresy, že všech pět stránek bude mít stejnou adresu v cachi. Pokud pak program bude tyto stránky procházet, nepodaří se je do cache dostat, neboť na jedné adrese čtyřcestné cache mohou být pouze čtyři řádky. I když má L2 cache značnou velikost 512kB, je možné, že se pět nevhodně umístěných stránek o celkové velikosti 20kB do téhle cache nevejde.

Aby k tomuto jevu nedocházelo, používá FreeBSD barvení stránek. Každá stránka má barvu, což je adresa dat v cachi. Například pokud máme čtyřcestnou cache o velikosti 512kB a velikost stránky 4kB, stránky mají 32 barev. Alokátor stránek ve FreeBSD se snaží přidělovat stránky takové barvy, která odpovídá virtuální adrese, na níž bude stránka namapována. Pokud například program alokuje pět stránek na virtuálních adresách 0, 4096, 8192, 12288 a 16384, budou tyto stránky mít barvy 0, 1, 2, 3, 4. Touto strategií se zabrání výše zmiňovanému jevu, kdy několik stránek má stejnou barvu (čili stejnou adresu v cachi) a tyto stránky se pak do cache nevejdou. Implementace barvení stránek je jednoduchá — pro každou barvu existuje fronta volných stránek, které onu barvu mají. Při požadavku o stránku se nejprve bere stránka z fronty s požadovanou barvou. Pokud je fronta prázdná, vezme se stránka z fronty s nejvzdálenější barvou. Je-li tato fronta taktéž prázdná, procházejí se ostatní fronty. Parametr index funkce vm_page_alloc se používá k určení požadované barvy stránky.

Otázka, zda barvení stránek pomáhá, nebo nepomáhá zvýšit rychlost běhu programů, je sporná. Tvůrci Linuxu tvrdí, že barvení zbytečně zesložiťuje jádro a jeho efekt je zanedbatelný, a proto ho nechtějí implementovat. Protože tvůrci FreeBSD barvení implementovali, tvrdí, že barvení pomáhá při zvýšení rychlosti. Realita je asi taková, že:

• Pokud program alokuje několikrát méně paměti, než je velikost L2 cache, pak pokud barvení stránek nebude použito, je malá pravděpodobnost, že bude mít spousta stránek stejnou barvu. Proto v takovém případě nemá barvení velký vliv.
• Pokud program alokuje několikrát více paměti, než je velikost L2 cache, a náhodně na tuto paměť přistupuje, tak se stránky do cache stejně nevejdou a vůbec nezáleží na tom, zda je barvení použito, nebo ne.
• Pokud program alokuje množství paměti srovnatelné s velikostí L2 cache, má barvení stránek význam. Náhodným přidělováním stránek bez barvení se nedosáhne rovnoměrného rozdělení barev a pokrytí celé cache. Naproti tomu barvení zajistí, že cache bude rovnoměrně pokrytá a že program dostane přesně takové množství stránek se stejnou barvou, jaká je asociativita cache. Díky tomu se celá datová oblast programu vejde do cache.