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

Struktury virtuální paměti na FreeBSD

Každá fyzická stránka paměti je popsána strukturou struct vm_page. Každá stránka náleží do právě jednoho objektu ( struct vm_object). Objekty tvoří stromy — každý objekt může mít jeden „backing object”. Některé objekty backing objekt mít nemusí. Každému cachovanému souboru v paměti náleží jeden objekt. Každému procesu náleží objekt, který popisuje paměť alokovanou tímto procesem. Každému segmentu sdílené paměti náleží také jeden objekt. Každý objekt má„backing store” — je to oblast, kam se budou stránky zapisovat a ze které se budou zpět natahovat. Pro objekty náležející souborům je backing store daný soubor; pro objekty paměti procesů nebo sdílené paměti je backing store swapová oblast. Každý proces má jednu struct vmspace, která popisuje jeho virtuální adresní oblast. struct vmspace má kruhový seznam struktur struct vm_map_entry  — každá vm_map_entry odpovídá jednomu segmentu namapovanému pomocí mmap. vm_map_entry obsahuje ukazatel na vm_object a adresu, na kterou je tento objekt namapován.

Popis virtuálního adresního prostoru

Struktura struct vmspace má položku struct pmap, která obsahuje informace pro virtuální prostor procesu závislé na architektuře. Každá stránka má kruhový seznam struktur struct pv_entry. Každá pv_entry odpovídá jednomu mapování této stránky. pv_entry je struktura závislá na architektuře. Tyto struktury jsou alokovány v poli fixní velikosti určené při bootu systému. Pokud pole přeteče, jsou stránky odmapovány. Bylo by efektivnější struktury alokovat dynamicky. S mapováním se manipuluje pomocí obecných funkcí, jako například void pmap_enter(struct pmap *pmap, unsigned long vm_offset, struct vm_page *page, vm_prot_t prot, boolean_t wired). Tato funkce namapuje stránku do adresního prostoru procesu. Prvním parametrem je adresní prostor, druhým parametrem je adresa v tomto prostoru, třetím parametrem je stránka, čtvrtým parametrem jsou práva přístupu a posledním parametrem je příznak určující, že mapování nesmí být zrušeno v případě nedostatku paměti. Implementace této a podobných funkcí je závislá na architektuře, ale rozhraní je pro všechny architektury stejné. To umožňuje systém virtuální paměti rozdělit na část závislou na architektuře a na část nezávislou na architektuře. O správu tabulek stránek se stará kód v souboru pmap.c a zbytek systému virtuální paměti pouze volá funkce tohoto souboru, pokud potřebuje nějakou stránku namapovat nebo odmapovat.

Při výpadku stránky systém najde vm_map_entry a objekt, kde k výpadku došlo. Pokud se požadovaná stránka nachází v objektu, natáhne se z jeho backing store a namapuje se. Pokud se stránka v objektu nenachází, hledá se dále v backing objektu tohoto objektu. Je-li stránka nalezena v backing objektu, provede se její kopie (pokud se při výpadku stránky zapisovalo) a nová stránka se uloží do aktuálního objektu. Pokud v backing objektu stránka není, hledá se v backing objektu tohoto objektu, a tak se postupuje dále až ke kořeni stromu objektů. Pokud stránka není ani tam, vytvoří se prázdná stránka a ta se uloží do nejhornějšího objektu, kde výpadek stránky vznikl.

Nové dva vm objekty vzniklé po provedení fork

Objekty se vytvářejí následovně:

• Proces dostane jeden objekt pro jeho alokovanou paměť (alokace pomocí malloc se vnitřně děje přes mmap s příznakem MAP_ANONYMOUS).
• Pokud proces udělá fork, vyrobí se dva nové objekty pro dva pokračující procesy. Oba objekty nemají na počátku žádné stránky a mají backing store nastavený na swapovou oblast. Původní objekt již nenáleží žádnému procesu, ale stane se z něj backing objekt pro oba nové objekty. Zde vidíme, že začne fungovat copy-on-write: při výpadku stránky se stránka nenalezne v objektu procesu, začne se vyhledávat v backing objektu, kde je nalezena, a pořídí se její kopie.
• Pokud proces namapuje soubor pro čtení nebo pro sdílený zápis, vytvoří se map_entry, která bude ukazovat na objekt příslušející souboru.
• Pokud proces namapuje soubor pro privátní zápis, vytvoří se nový objekt pro modifikované stránky souboru. Objekt má backing store swap a neobsahuje na počátku žádné stránky. Backing objekt pro tento nový objekt je nastaven na objekt příslušející namapovanému souboru. Pokud bude proces do stránek zapisovat, budou tyto kopírovány ze souboru do privátního objektu a v něm budou modifikovány.

Datové struktury sice vypadají složitě, ale požadavky splňují dokonale.

FreeBSD má novou vlastnost nazvanou IOOPT (povolení této schopnosti se provádí přidáním řádku „options ENABLE_VFS_IOOPT” do konfiguračního souboru, překompilováním jádra a nastavením sysctl vfs.ioopt=1). IOOPT spočívá v tom, že pokud proces čte velký soubor pomocí funkce read, není tento soubor kopírován do adresního prostoru procesu, ale stránky se souborem jsou do adresního prostoru namapovány. Funguje to samozřejmě pouze, pokud je adresa čtení a offset v souboru na hranici stránky. Pokud proces do takových stránek zapíše, provede se copy-on-write. Copy-on-write se ovšem také musí provést, pokud do souboru zapíše jiný proces pomocí funkce write. IOOPT je experimentální vlastnost, není implicitně povolená a je možné, že bude obsahovat chyby.

Struktury virtuální paměti na Linuxu

Linux má výrazně jednodušší správu virtuální paměti. Je vidět, že memory management na Linuxu vznikal spontánně, bez většího rozmyšlení. Původní Linux 0.01 měl jen copy-on-write po fork, neměl mapování ani sdílení stránek. V kódu jsou vidět poznámky Linuse „dnes jsem udělal load-on-demand”, „dnes jsem udělal sdílené stránky” a podobné. Page cache přišla až v Linuxu 2.0.

Pro každou fyzickou stránku existuje struktura struct page. Každá stránka má počítadlo použití — toto počítadlo určuje, z kolika míst někdo na stránku ukazuje. Funkce pro uvolnění stránky free_pages toto počítadlo zmenší o jedna a stránku uvolní pouze v případě, že počítadlo dosáhne nuly. Tím je zajištěno, že nebude uvolněna stránka, na kterou se někde nějaký kód odkazuje. Seznam mapování, podobně jako u FreeBSD, existuje až od Linuxu 2.6. Linux nemá žádné vm objekty. Na stránky ukazuje ukazatel z tabulky stránek procesu a/nebo jsou v hashové tabulce inody souboru, ke které náleží. Každý proces má struct mm_struct, která popisuje jeho adresní prostor (je to ekvivalent struct vmspace na FreeBSD). mm_struct obsahuje AVL-strom struktur struct vm_area_struct. Každá vm_area_struct odpovídá jednomu segmentu namapovanému pomocí mmap (je to ekvivalent vm_map_entry na FreeBSD). Struktury jsou uloženy ve vyváženém stromě, takže vyhledávání je rychlejší než vyhledávání v lineárním seznamu. vm_area_struct ukazuje rovnou na soubor, který je namapován — objekty zde neexistují.

AVL strom popisující virtuální adresní prostor procesu

Linux ukládá informace do samotných tabulek stránek. Pokud je stránka namapovaná, je možno zjistit struct page přímo z tabulky stránek po vhodném přepočítání fyzické adresy na offset do pole stránek. Pokud je stránka odswapovaná, do tabulky stránek se zapíše ukazatel do swap souboru, kde se stránka nachází. Linux nemá tak striktně jako FreeBSD oddělenou část závislou a nezávislou na architektuře. Celý kód správy paměti v Linuxu předpokládá, že poběží na systému s tříúrovňovými tabulkami stránek. Velikost těchto tabulek stránek a makra pro bitovou manipulaci s nimi jsou v hlavičkových souborech příslušejících každé architektuře. Pokud Linux běží na architektuře s dvouúrovňovými tabulkami stránek (například IA32), jsou tato makra udělaná tak, že předstírají, že prostřední tabulka stránek má jen jednu položku. Tento přístup je sice jednodušší než na FreeBSD, ale má menší schopnosti — například na 64bitových architekturách není možno pokrýt celý 64bitový adresní prostor, neboť na to tabulky stránek tří úrovní nestačí. Na architekturách, které nemají vůbec tabulky stránek (jako například Sparc64), se přesto tabulky stránek musejí vytvářet.

Tabulky stránek, stránky a struktura address_space

Při provedení fork Linux zkopíruje strom vm_area_struct a tabulky stránek. Anonymní alokované stránky nastaví jako read-only. U všech stránek zvětší jejich počítadlo použití, neboť na stránky se již odkazují dvě tabulky.

Při výpadku stránky Linux najde danou vm_area_struct a položku tabulky stránek. Pokud je položka tabulky stránek nulová, je buď alokována a vynulována nová stránka (pokud se jedná o anonymní alokovanou paměť), nebo je stránka natažena ze souboru (pokud se jedná o namapovaný soubor). Pokud položka tabulky stránek není nulová (ale má vynulovaný „present” bit), předpokládá se, že ukazuje do swap souboru, a stránka je odtud natažena. Pokud dojde k pokusu o zápis do read-only stránky, Linux se podívá na počítadlo použití. Pokud je jedna, nastaví položku tabulky stránek na read-write a pokračuje. Pokud je více než jedna, provede kopii stránky a tuto nastaví jako read-write v tabulce stránek. Tak je zajištěna funkce copy-on-write při provádění fork.

Mapa swapu má pro každou stránku swap oblasti počítadlo použití. Pokud je nulové, stránka je volná. Pokud je jedna, ve stránce se nacházejí data. Pokud je větší než jedna, jedná se o odswapovanou stránku sdílenou po forku.

Po zapsání stránky do swap oblasti není stránka uvolněna, ale je umístěna do tzv. swap cache. Do swap cache se rovněž umisťují stránky ihned po natažení ze swap oblasti. Swap cache je hashovaná podobně jako stránky náležející souborům. Nacházejí se v ní stránky, které jsou jak ve swapu, tak v paměti. Do těchto stránek je zakázáno zapisovat — při pokusu o zápis se stránka ze swap-cache odstraní a její místo ve swapové oblasti je odalokováno. Stránky ve swap cachi je možno kdykoli uvolnit a není třeba je zapisovat do swapové oblasti. Swap cache zajišťuje, že pokud program bude procházet velké množství stránek a tyto stránky bude pouze číst, tak se stránky umístí do diskové swap oblasti i do swap cache a pak se budou z disku pouze číst, aniž by bylo nutno je zapisovat zpět.

Výše popsané principy umožňují splnit téměř všechny požadavky na virtuální paměť, které byly specifikovány — vyjma jediného — sdílená paměť. Sdílení stránek po fork a jejich copy-on-write funguje, ale sdílení stránek alokovaných pomocí SYSV SHM a jejich swapování zde není možno jednoduše implementovat. Verze Linuxu 2.2 a nižší to měly udělané značně komplikovaně — bylo vidět, že tam sdílená paměť byla uměle dodělávána. Linux 2.4 na sdílenou paměť pohlíží jako na filesystém (TMPFS), který nemá žádné fyzické blokové zařízení a jehož stránky jsou zapisovány do swapu. Používání sdílené paměti je implementováno jako mapování stránek z tohoto filesystému. Pokud uživatel chce, může si TMPFS i namountovat někam do adresářového stromu a mít pak filesystém, jehož obsah se ukládá do paměti a swapuje se do swapové oblasti. Zavedením TMPFS byl kód obsluhující sdílenou paměť výrazně zjednodušen.

Linux 2.6 má novou vlastnost — reversní mapování (rmap). Je to podobné jako pv_entry na FreeBSD. Ke každé stránce existuje seznam jejích mapování. Rmap je implementován méně paměťově náročně než na FreeBSD — struktura struct pte_chain se vytváří pouze tehdy, je-li stránka sdílena více mapováními (v opačném případě je ukazatel na mapování rovnou v struct page). struct pte_chain obsahuje pole ukazatelů na mapování, v případě zaplnění pole se alokuje nová struct pte_chain a přidá se do jednoduše linkovaného seznamu. Existuje tedy overhead 4 byty na mapování. Na FreeBSD naproti tomu existuje overhead 28 bytů na mapování (velikost struct pv_entry). Rmap se používá pro snadné zjištění, jak moc je stránka používána procesy, pro algoritmus výměny stránek.

Linux 2.6 má rovněž celý memory management rozdělen na struktury pg_data_t pro účely NUMA. NUMA je mnohoprocesorový stroj, na kterém je různá doba přístupu procesorů k jednotlivým částem paměti. Na NUMA stroji existují NODY, každá se skládá z několika procesorů a jejich paměti. Procesory přistupují rychle k paměti na svojí nodě a pomalu k pamětem na ostatních nodách. V Linuxu existuje pro každou nodu jedna struktura pg_data_t, která obsahuje seznam stránek a informace pro algoritmus výměny stránek pro tuto nodu.

Závěr: Linuxový memory management je podstatně jednodušší než na FreeBSD a obsahuje mnohem menší množství struktur. Nelze jednoznačně rozhodnout, zda je to lepší, nebo ne. Menší množství struktur znamená kratší čas strávený jejich údržbou a tedy větší rychlost. Na druhou stranu absence seznamu mapování stránky může výrazně zpomalit prohledávání na uvolnitelné stránky (na FreeBSD se ke stránce ihned najde seznam všech mapování; je vidět, zda je stránka nepoužitá, a taková se pak uvolní; na Linuxu se musí procházet všechny tabulky stránek a stránka se uvolní, až když je odmapovaná ve všech tabulkách). FreeBSD IOOPT je na Linuxu také naprosto neimplementova­telné, neboť jednoduché struktury Linuxu tak složité operace se stránkami neumožňují.