Mapování stránek v jádře
V předchozí kapitole jsme si popsali alokaci stránek a nyní nastává otázka, jak k nim přistupovat. V současných systémech se množství fyzické paměti blíží velikosti virtuálního adresního prostoru nebo ji i překračuje. Procesory Pentium mohly mít maximálně 4G fyzické paměti a 4G virtuální paměti. Pentium Pro může adresovat až 64G fyzické paměti a 4G virtuální paměti. Pokud má systém více fyzické paměti než virtuální, nemohou být všechny stránky současně namapované a je třeba řešit situace, jak stránky mapovat. V této kapitole se budeme zabývat procesory IA32. U 64bitových procesorů je situace výrazně lepší — tyto procesory mohou adresovat mnohem větší množství virtuální paměti, a tak zde nehrozí nebezpečí, že by fyzické paměti bylo více než virtuální.
Na Linuxu 2.2 a nižších je třeba mít vždy celou fyzickou paměť namapovanou do adresního prostoru jádra. Jádro má 1G virtuálních adres, uživatelské programy mají 3G. Z čehož plyne, že takové jádro může používat maximálně 1G paměti. Jádro je možno upravit tak, aby jeho adresní prostor byl 2G a uživatelské programy dostaly také 2G; s touto úpravou tedy je možno jádro používat na strojích s maximálně 2G paměti. Toto řešení není dostatečné, proto byl způsob mapování paměti v jádrech 2.4 změněn.
Linux 2.4 dělí paměť na zóny. Typicky máme tři zóny — zónu použitelnou pro ISA DMA o velikosti 16M (tato zóna existovala i na předchozích jádrech), zónu přímo namapovaných stránek, která má velikost 1G, a highmem zónu nenamapovaných stránek, která obsahuje všechny zbývající stránky nad hranicí 1G až do potenciálního limitu 64G na Pentiu Pro. Příznak __GFP_DMA určuje, že alokace musí být z ISA DMA zóny. Příznak __GFP_HIGHMEM určuje, že alokace může být z highmem zóny. Pokud není ani jeden příznak uveden, alokuje se z přímo namapované zóny, a pokud ta je prázdná, tak z ISA DMA zóny. Paměť o fyzických adresách 0 až 1G je permanentně namapovaná na virtuální adresy 3G až 4G (nejedná se přesně o 1G, je to trochu méně, aby v jádře ještě nějaké virtuální adresy zbyly). Z této paměti se alokují všechny struktury jádra. Je totiž potřeba, aby struktury jádra byly vždy dostupné. Z highmem zóny se alokují stránky uživatelských procesů a stránky diskové cache. U těchto stránek není potřeba, aby byly vždy přístupné jádru. Pokud jádro potřebuje přistupovat na nenamapovanou stránku, musí použít funkci void *kmap(struct page *) pro její namapování do virtuálního adresního prostoru jádra a void kunmap(struct page *) pro odmapování. Tyto funkce udržují cache 512 nebo 1024 naposledy namapovaných stránek; pokud stránka je už namapovaná v cachi, vrátí adresu, pokud není namapovaná, tak odmapují nějakou stránku z cache a požadovanou stránku namapují, pokud jsou všechny stránky v cachi právě používané, proces se zablokuje a čeká, než se nějaké mapování neuvolní. Toto mapování se provádí například při nulování čerstvě alokovaných uživatelských stránek nebo při kopírování stránek po provedení syscallu fork.
Při přechodu na nový způsob mapování stránek v jádrech 2.4 vznikl problém se starými ovladači zařízení. Například ovladače disku dostávají virtuální adresu dat a vyžadují, aby tato adresa byla namapovaná. Nejsou tedy schopny dělat I/O do highmem zóny. Řešením jsou bounce-buffery — pokud se má dělat I/O z nebo do highmem zóny, alokuje se dočasný bounce-buffer v namapovaná zóně, do něho se udělá I/O a data se kopírují. Pokud se provádí zápis, data se kopírují před zápisem do bounce-bufferu, pokud se provádí čtení, data se kopírují po čtení z bounce-bufferu. Problém je vyřešen, ovšem s nepříjemným důsledkem — data se občas kopírují, ačkoli by se kopírovat nemusela. Například PCI IDE DMA může pracovat s adresami až do 4G. Nicméně pokud děláme I/O v rozsahu 1G až 4G, musíme použít bounce-buffer, protože ovladač IDE neumí pracovat s nenamapovanými adresami. Použití bounce-bufferu a kopírování dat zpomaluje přístup na disk. V experimentálních jádrech 2.6 je tento problém již vyřešen — ovladače IDE a SCSI disků byly modifikovány tak, aby mohly pracovat s nenamapovanými buffery, a bouncování se používá opravdu jen tehdy, když je nutné — tedy při práci s daty nad 4G, pokud architektura neumožňuje mapování adresního prostoru PCI, které bude popsáno v následující kapitole.
Pro Linux 2.6 existuje speciální 4G/4G patch — tento patch způsobí, že jádro i každý uživatelský proces dostanou plných 4G adresního prostoru. Při vstupu i výstupu z jádra je přepnuta tabulka stránek. Přepnutí tabulky stránek je na IA32 poměrně pomalé — dojde totiž k vyprázdnění TLB cache a spousta následujících přístupů do paměti čeká při načítání z tabulky stránek (lepší architektury jsou schopny v TLB uchovávat současně více mapování pro různé kontexty, tudíž tam tenhle problém nenastává). Patch není ve standardním jádře, takže není zaručena jeho stabilita. Měl by být používán pouze ve speciálních případech, kdy je velký adresní prostor potřeba — ve většině normálních případů totiž přinese značné zpomalení.
FreeBSD funguje zcela jinak. Implicitně nemá namapovanou žádnou paměť a stránky jádra mapuje do virtuální paměti po alokaci. Každá stránka je mapovaná zvlášť. FreeBSD nemá a ani nepotřebuje buddy alokátor. Pokud je pomocí funkce malloc požadována alokace bloku většího než stránka, alokuje se několik nesouvislých stránek a ty se v jádře namapují do souvislého bloku virtuální paměti. FreeBSD nemá a nepotřebuje zóny pro paměť jádra a paměť procesů, jako má Linux, neboť na FreeBSD je možno kteroukoli stránku namapovat do jádra. Výhodou tohoto přístupu je, že odpadá buddy alokátor a alokace velkých bloků je zaručená. Nevýhodou je, že FreeBSD neumí používat velké stránky (na určitých architekturách (např. IA32 nebo Alpha) je možno pomocí speciálního příznaku u položky adresáře tabulek stránek říct, že tato položka se neodkazuje na tabulku stránek nižší úrovně, ale rovnou na stránku větší velikosti (na IA32 je to 4M nebo 2M). Podobně na Sparc64 se softwarově řízenou TLB je možno do TLB vkládat stránky různé velikosti. Takové větší stránky jsou rychlejší, neboť pak dochází k méně TLB-missům.) k mapování paměti jádra (FreeBSD používá velké stránky pouze k mapování kódu jádra, neboť ten je statický) (pozn. red.: Taky jste se v tomhle souvětí ztratili? –Johanka). Linux naproti tomu se svým pevným mapováním paměti velké stránky používá.
Mapování stránek pro DMA
I když máme 64bitový procesor s 64bitovou fyzickou a virtuální adresu, začnou se při překročení hranice 4G objevovat problémy s PCI kartami. Zařízení na sběrnici PCI mohou adresovat paměť pouze 32bitově. Existuje sice i rozšíření PCI pro 64bitové adresování, nicméně to je jednak pomalejší, jednak je nepodporují všechny karty. Na PCI neexistuje žádný DMA řadič podobně, jako třeba na ISA; na PCI si každé zařízení dělá adresaci paměti samo. Tato technika se nazývá Bus-master. Aby se problémům s 4G limitem bylo možno vyhnout, některé 64bitové architektury (např. Sparc64 nebo Alpha) obsahují IOMMU neboli I/O Memory-management unit. Tato jednotka zajišťuje překlad adres podle zadané tabulky mezi 32bitovou PCI sběrnicí a 64bitovou paměťovou sběrnicí. Pokud chce nějaký ovladač provádět DMA přenos mezi pamětí a PCI zařízením, musí paměť namapovat do PCI adresního prostoru. K tomu se na Linuxu používjí funkce dma_addr_t pci_map_single(struct pci_dev *hwdev, void *ptr, size_t size, int direction); a void pci_unmap_single(struct pci_dev *hwdev, dma_addr_t dma_addr, size_t size, int direction);. Existují ještě podobné funkce pci_map_sg a pci_unmap_sg, které mapují několik paměťových bloků uvedených v seznamu. Na architekturách, které nemají IOMMU, jako například IA32, pci_map_single pouze převede virtuální adresu na fyzickou (neboli odečte od ní 3G) a pci_unmap_single neudělá nic. Na architekturách s IOMMU pci_map_single najde nějakou nepoužitou virtuální adresu v tabulce IOMMU, na ni namapuje požadovanou fyzickou adresu a zpátky předá tuto virtuální adresu. Ovladač předá virtuální adresu PCI zařízení a zařízení na tuto adresu bude dělat DMA. Na architekturách, které nemají automatickou synchronizaci cache procesoru s DMA, tyto funkce navíc synchronizaci cache provádějí.
Na 64bitových architekturách máme díky IOMMU možnost dělat DMA do celé paměti a můžeme se vyhnout dělání paměťových zón. Nicméně programování IOMMU při každém přenosu (a tedy například při každém packetu ze sítě) zpomaluje. Rozhodně nepovažuji za šťastnou volbu, že IOMMU je povolena i v případech, kdy je v systému méně nebo rovno 4G paměti. Také nemusí být moc příjemné, že se i na architekturách, které IOMMU nemají, musí vyrábět zcela zbytečná struktura struct scatterlist, která popisuje mapování nespojitých bloků pro funkce pci_map_sg a pci_unmap_sg.
FreeBSD 4 neumí používat IOMMU a odtud plyne jeho limit pro maximum 4G paměti. I když jádro FreeBSD by bylo možné snadno přizpůsobit pro libovolné množství paměti, nastanou problémy s I/O zařízeními, neboť ta více než 4G adresovat neumějí. Na architekturách bez IOMMU (jako např. IA32) Linux používá zóny; FreeBSD zóny nemá, stránka může být alokovaná kdekoli, a proto by tam vznikl problém s DMA.
FreeBSD 5 má tyto nedostatky odstraněny — ovladače zařízení mají sjednocený přístup k DMA pomocí funkcí bus_dmamap_load a bus_dmamap_unload. Synchronizaci s cachemi procesoru musí speciálně provádět pomocí funkce bus_dmamap_sync. Tyto funkce umí naprogramovat IOMMU na architekturách, které IOMMU používají, případně použijí bounce-buffery na architekturách, které IOMMU nemají. FreeBSD 5 tedy umí pracovat s pamětí nad 4G. Nutno upozornit na celkem závažný problém, který tento přístup má — zatímco na Linuxu jsou struktury jádra alokovány vždy v části paměti přístupné pro DMA, na FreeBSD tomu tak nemusí být — může tedy docházet k výraznému zpomalování způsobenému kopírováním dat do bounce-bufferů například při prací se síťovými packety, pokud struktura popisující packet není náhodou alokována v dolních 4G. Na architekturách s IOMMU tento problém nenastane.
Závěr: Na 32bitových architekturách (např. IA32): Pokud máme méně než 1G paměti, oba systémy to zvládnou bez problémů. Pokud máme 1G až 4G, bude na Linuxu 2.4 zpomalen přístup na disk kvůli zbytečným bounce-bufferům; zatímco na FreeBSD to poběží rychleji. (V případě, že máme méně nebo rovno 2G, tak by asi bylo vhodné modifikovat jádro Linuxu tak, aby mělo 2G virtuální paměti pro procesy a 2G virtuální paměti pro jádro — pak se vyhneme zónám a bounce-bufferům). Linux 2.6 používá bounce-buffery jen tehdy, když jsou skutečně potřeba. V případě, že máme více než 4G, je třeba použít Linux, neboť to FreeBSD 4 neumí. FreeBSD 5 umí přistupovat k libovolnému množství paměti, ale nepoužívá zóny, což může vést k výraznému zpomalení DMA na síťových bufferech. Je nutné si uvědomit, že paměť, do které nelze dělat DMA (t.j. na Linuxu 2.4 nad 1G — při modifikování jádra 2G; FreeBSD a Linux 2.6 dělá DMA do celých 4G), je nepoužitelná jako cache (pokud je už jako cache použita, je hodně pomalá). Je použitelná pouze jako alokovaná paměť procesů, proto by se takové množství paměti mělo instalovat jen tehdy, máme-li program, který ji využije. Je zbytečné dávat takové množství paměti do serveru, neboť tam se většina paměti jako cache používá.
Na 64bitových architekturách: FreeBSD 4 má limit 4G paměti; Linux a FreeBSD 5 zvládnou libovolné množství paměti bez jakéhokoli zpomalování způsobeného větším množstvím paměti. Drobné zpomalení může přinést programování IOMMU. Paměť je použitelná pro libovolné účely, žádné limity neexistují.
Alokace struktur v jádře
Stránka je dost velká a v jádře je často potřeba alokovat velmi malé struktury. U alokace struktur se upustilo od alokování z klasické haldy za použití funkcí malloc a free, protože je to moc pomalé. Byla implementována rychlejší metoda — princip je stejný na obou systémech; na Linuxu se nazývá SLAB CACHE alokátor a na FreeBSD ZONE alokátor (nemá to nic společného se zónami pro alokaci stránek na Linuxu).
Než chce nějaký subsystém v jádře alokovat nějakou strukturu, musí v SLAB alokátoru registrovat typ struktury — v Linuxu se to dělá pomocí funkce kmem_cache_create. Funkce jako parametr dostane velikost, příznaky, konstruktor a destruktor (mohou být NULL). Funkce vyrobí slab cache, což je v podstatě seznam stránek a v každé stránce seznam objektů. Ze slab cache je možno strukturu alokovat pomocí funkce kmem_cache_alloc. Jako parametr dostane funkce příznaky — zda má být alokace atomická nebo se proces může zablokovat. Uvolnit strukturu je možno pomocí funkce kmem_cache_free. Konstruktor je možno použít k inicializaci některých položek struktury. Je třeba zajistit, aby při uvolnění struktury byly všechny její položky ve zkonstruovaném stavu, neboť konstruktor je volán pouze jednou.
Na rozdíl od funkcí malloc a free z libc (a jejich typických implementací typu „first-fit”, „next-fit”, „best-fit” apod.) mají funkce slab alokátoru konstantní složitost — kmem_cache_alloc pouze vezme jednu stránku, ze seznamu volných objektů odebere jeden objekt, a ten vrátí. Protože všechny objekty mají stejnou velikost, není třeba hledat blok dostatečné velikosti tak, jak to dělá většina implementací malloc. Pokud kmem_cache_alloc žádnou stránku s volným objektem nenalezne, alokuje novou stránku a zavolá konstruktor na každý objekt v této stránce. Aby se zjednodušilo hledání stránek, jsou udržovány seznamy plných stránek, částečně plných stránek a prázdných stránek. Z prázdných stránek je alokováno, pokud už nejsou žádné částečně plné stránky, aby se omezila fragmentace paměti. Pokud dochází paměť v systému, jsou prázdné stránky uvolněny. Předtím je ještě na uvolňované objekty zavolán destruktor. Destruktory se příliš nepoužívají. Na SMP jsou použity speciální malé seznamy volných struktur pro každý procesor zvlášť, aby při alokaci nebylo nutno zamykat celou slab cache a nedocházelo k přelévání dat mezi procesorovými cachemi.
Pro lepší využití cache Linux používá barvení. Užitek barvení můžeme vidět na následujícím příkladu: máme velikost řádky cache 32 bytů a velikost struktury 64 bytů. Alokované struktury jsou zřetězeny v seznamu a tento seznam je procházen; při projití se však sáhne pouze na prvních 32 bytů dané struktury. Pokud by struktury byly alokovány bez barvení, tak by tahle operace projití seznamu stresovala sudé adresy v L1 cachi a vůbec by nevyužívala liché adresy. Aby byly všechny adresy cache použity rovnoměrně, objekty v dalších alokovaných stránkách jsou vždy posouvány o velikost řádky cache.
Linux má i funkce kmalloc a kfree, které jsou ekvivalentní funkcím malloc a free z libc. Tyto funkce jsou implementovány pomocí slab alokátoru — při startu se předalokují speciální slab cache pro objekty o velikosti mocniny dvojky a kmalloc zavolá kmem_cache_alloc pro slab objektů příslušné velikosti.
FreeBSD má podobnou implementaci nazvanou ZONE alokátor. FreeBSD neumožňuje použití konstruktorů a destruktorů. Zónu vytvoříme pomocí funkce zinit. Ze zóny se alokuje pomocí funkce zalloc a uvolňuje pomocí zfree. Zóny na FreeBSD nejsou nikdy zmenšovány. Proto nejsou potřeba seznamy plných/částečně plných/prázdných stránek. Stačí jen jeden seznam všech volných struktur. FreeBSD nemá barvení; ve zdrojovém kódu je poznámka, že kdysi tam barvení bylo, ale způsobovalo to zpomalení (což je docela dobře možné — při procházení dlouhého seznamu neobarvených struktur se přemaže jen část cache, zatímco při procházení dlouhého seznamu obarvených struktur se přemaže celá).
FreeBSD má rovněž malloc a free — algoritmus alokace je stejný jako na Linuxu, ale je napsaný zvlášť a nepoužívá zóny.
