Hlavní navigace

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

Mikuláš Patočka

Dnešním tématem seriálu o vnitřnostech operačních systémů budou VFS, dozvíme se zejména podrobnosti o vyrovnávacích pamětech.

VFS — rozhraní pro přístup k filesystému

Aby jádro mohlo pracovat s více druhy filesystémů, bylo vytvořeno rozhraní mezi jádrem a ovladačem filesystému nazvané VFS (virtual filesystem). VFS je soubor funkcí, které může ovladač filesystému volat, a soubor funkcí, které musí jádru poskytnout. Nejstarší část VFS je bufferová cache. Bufferová cache existuje již v původním Unixu z Bellových laboratoří, z dob, kdy ještě žádné VFS neexistovalo a jádro mělo v sobě napevno „zadrátovaný” jeden filesystém (původní Linux měl také zadrátován pouze jeden filesystém (minixfs). VFS a podpora dvou filesystémů (minixfs a extfs) se objevily až v jádře 0.96c).

Bufferová cache

Každý buffer má hlavu (struktura struct buffer_head na Linuxu a struct buf na FreeBSD) a datovou oblast. Hlava obsahuje různé příznaky a informace o bufferu (např. blokové zařízení, ke kterému buffer náleží, číslo bloku, zda jsou data platná, zda je potřeba buffer uložit na disk, zda je právě prováděno čtení nebo zápis dat a podobně). Hlava také obsahuje pointer na datovou oblast. V datové oblasti se nacházejí data načtená z disku pro příslušný blok. Existuje hashová tabulka všech bufferových hlav, ve které je možno podle blokového zařízení a čísla bloku vyhledat buffer. Základní operace na bufferové cachi jsou

  • struct buffer_head *bread(blokové zařízení, číslo bloku, velikost bloku)  — tato funkce vyhledá v hashové tabulce buffer. Najde-li buffer, zkontroluje, zda je na něm právě prováděna operace čtení. Pokud ano, počká na příslušné frontě, až operace skončí. Jestliže operace čtení neprobíhá, zkontroluje, zda jsou data platná. Pokud ano, vrátí buffer, pokud ne, spustí tato funkce sama operaci čtení a počká. Když není buffer nalezen v hashové tabulce, je vytvořen, vložen do tabulky, je na něm zahájena operace čtení a funkce počká, než tato operace skončí. Po návratu této funkce je buffer v zamčeném stavu — t.j. nemůže být uvolněn z paměti.
  • void brelse(struct buffer_head *)  — odemkne buffer dříve zamčený funkcí bread. Jádro může odemčený buffer kdykoli uvolnit (dělá to zpravidla, pokud dochází paměť). Proto se strukturou buffer_head, která ukazuje na odemčený buffer, již není možno dále pracovat.
  • void mark_buffer_dirty(struct buffer_head *) na Linuxu a ekvivalentní void bwrite(struct buf *) na FreeBSD — označí buffer jako modifikovaný. Pokud kód filesystému zavolá bread, může pak obsah datové oblasti bufferu modifikovat a po provedení tohoto modifikování musí zavolat zmíněnou funkci. Tím jádru dává najevo, že je potřeba, aby buffer byl uložen zpátky na disk. Buffer není zpravidla uložen hned (pokud není zapnutý synchronní zápis na filesystému), ale je uložen až někdy později, aby filesystém zbytečně nemusel čekat na dokončení operace zápisu.
  • void bforget(struct buffer_head *)  — funguje podobně jako brelse, až na to, že buffer okamžitě uvolní z cache, a pokud je modifikovaný, nezapisuje ho na disk. Používá se poté, co filesystém odalokoval nějakou strukturu na disku po provedení unlink, truncate nebo rmdir  — v takovém případě již nemá smysl uvolněná data dále držet v cachi nebo je zapisovat na disk, protože se na ně filesystém již neodkazuje.
  • void ll_rw_block na Linuxu a VOP_STRATEGY na FreeBSD — spustí čtení nebo zápis na bufferu. Funkce se ihned vrátí, na výsledek je třeba počkat pomocí wait_on_buffer nebo tsleep.

Bufferová cache umožňuje ovladači filesystému velmi efektivně pracovat s daty na disku. Pokud se buffer nachází v cachi, je operace bread velmi rychlá — v podstatě se provede pouze vyhledání v hashové tabulce a zvýšení počítadla zámků. Nedochází přitom ke kopírování dat. Taktéž další operace — brelse a mark_buffer_dirty  — jsou velmi rychlé.

Linux umí na jednom zařízení pracovat pouze s buffery stejné velikosti (tuto velikost specifikuje ovladač filesystému při mountování). FreeBSD umožňuje různé velikosti bufferů — to ovšem činí kód funkcí pro operace s buffery značně komplikovaný. Linux má maximální velikost bufferu jedna stránka. FreeBSD má maximální velikost bufferu 64k. Buffer zde může zabírat několik stránek, které jsou namapovány do souvislé oblasti ve virtuální paměti jádra. Na FreeBSD je při startu systému alokován pevný počet bufferových hlav a hlavy již nemohou přibývat (ale paměť alokovaná pro datovou oblast bufferů se může zvětšovat i zmenšovat). Linux umí bufferové hlavy alokovat a uvolňovat za běhu podle potřeby.

Inodová cache

Bufferová cache by sama o sobě stačila k omezení přístupu na disk. Na původním Unixu to byla jediná cache. Postupem času se však začaly objevovat další cache (inode, dentry a page cache), které umožňují rychlejší přístup k vyšším strukturám filesystému. Na Linuxu je cache nazývána inodová; na FreeBSD vnodová. Pod pojmem „inode” se na Linuxu rozumí jak inoda uložená na disku, tak inoda uložená v paměti v cachi. Na FreeBSD se pojmem „inode” označuje pouze inoda na disku; inoda v cachi se nazývá „vnode”.

Inoda je objekt, který přísluší každému souboru a adresáři na filesystému. Inoda obsahuje různé informace o souboru — velikost, práva přístupu, časy vytvoření/modi­fikace/přístu­pu, informace o umístění datových bloků na disku a podobně. Inoda neobsahuje jméno souboru ani ukazatel na nadřazený adresář (aby bylo možno dělat hard-linky).

Inodová cache je hashová tabulka, ve které je možno podle dvojice (blokové zařízení, číslo inody) inodu vyhledat. Inoda má jednotný formát, ve kterém je v paměti v této cachi (na Linuxu struct inode, na FreeBSD struct vnode). Ovladač filesystému musí poskytnout dvě funkce — jednu, která přečte inodu z disku a překonvertuje ji do formátu v paměti, a druhou, která zapíše inodu nacházející se v paměti na disk. Tyto funkce používají bufferovou cache pro operace s diskem. Inoda v paměti má příznaky, zda je modifikovaná (a je tedy třeba ji zapsat), nebo zda je právě načítána z disku, což znamená, že položky jsou neplatné a nesmí se používat. Správu těchto příznaků, jakož i volání oněch funkcí ovladače filesystému, zajišťuje jádro. Na Linuxu dělá hashování inod samotné jádro; na FreeBSD dělá hashování vnod ovladač filesystému. Linux umí paměť obsaženou pro inody zmenšovat a zvětšovat podle potřeby; na FreeBSD dochází pouze ke zvětšování vnodové paměti až do uživatelem nastaveného limitu. Paměť vyhrazená pro vnody na FreeBSD není nikdy uvolňována (v některých částech jádra FreeBSD se s vnodami pracuje takovým způsobem, že si kód jádra zapamatuje pointer na vnodu, blokové zařízení a číslo vnody — a za dlouhou dobu (aniž by mezitím držel nějaký zámek na vnodě) se na pointer podívá, zjistí, zda je vnoda platná, porovná zařízení a číslo, a pokud souhlasí, začne s vnodou pracovat. Kdyby se paměť pro vnody uvolňovala, přestane tenhle mechanismus fungovat a náhodné bloky paměti budou považovány za vnody).

Cache pro vyhledávání v adresářích

Původně cache pro vyhledávání neexistovala. Ovladač filesystému poskytoval funkci lookup, která dostala jako parametr inodu (resp. vnodu) adresáře a jméno souboru a vracela inodu souboru s daným jménem v daném adresáři. Inodová cache zabránila čtení inod z disku, ale bylo třeba také zabránit pomalému vyhledání v adresáři. Na vyhledávání souboru v adresáři se používá bufferová cache, která sama o sobě zabrání opakovanému čtení z disku. Nicméně vzhledem k tomu, že adresář je sekvence dvojic (jméno souboru, inoda), je lineární prohledávání adresáře v bufferech velmi pomalé.

Na Linuxu byla původně hashová tabulka pro vyhledávání jmen k adresářům v ovladači filesystému, což s sebou přinášelo tu nevýhodu, že bylo třeba psát cache pro každý filesystém znovu. Na Linuxu 2.2 byla zavedena nová dentry cache, která funguje obecně pro všechny filesystémy. Každý filesystém obsahuje strom struktur struct dentry. Každá dentry obsahuje jméno souboru, rodičovskou dentry a ukazuje na inodu, které náleží (ale ne každá inoda musí mít dentry — dentry je možno uvolnit a inodu zachovat v paměti). Adresářová dentry má hashovou tabulku obsahující dentry příslušející položkám adresáře. Při vyhledávání souboru se nevolají žádné funkce filesystému, ale prochází se strom dentry. Když není dentry daného jména nalezena, vytvoří se prázdná dentry a zavolá se funkce filesystému lookup, která soubor nalezne a dentry vyplní. Při dalším hledání téhož souboru se již použije vytvořená dentry. Pokud funkce lookup jméno nenalezne, vytvoří tzv. negativní dentry. Negativní dentry informuje o tom, že soubor daného jména se v adresáři nevyskytuje. Když je při prohledávání stromu nalezena negativní dentry, tak se okamžitě vrátí chyba. Pokud se tedy program bude snažit opakovaně otevřít neexistující soubor, bude tato operace otevření velmi rychlá (v podstatě jen vyhledání v hashové tabulce) a nebude se při tom muset vyhledávat v adresáři. Při nedostatku paměti se uvolňuje jak dentry cache, tak inode cache. Je třeba zajistit, že nebude uvolněna inoda, na kterou ukazuje dentry, a nebude uvolněna dentry, která není listem stromu (t.j. má v hashové tabulce nějaké dentry). Se zavedením dentry cache definitivně padla možnost dělat hard-linky na adresáře, neboť kód jádra předpokládá, že dentry tvoří strom.

FreeBSD má podobnou cache jako Linux (i když byla udělána později než na Linuxu). Cache na FreeBSD nemá nutně podobu stromu — cache je udělána takovým způsobem, že ke každé adresářové vnodě je možno v cachi nalézt seznam souborů a podadresářů. Cache může obsahovat i negativní položky pro nenalezené soubory. Položky cache jsou alokovány pomocí funkce malloc, takže se po uvolnění vracejí do malloc poolu. Dříve FreeBSD sjednocenou vyhledávací cache nemělo, a tak byla cache napsána přímo do filesystému — tato cache tam pořád zůstala, takže v současné době jsou ve FreeBSD dvě cache obsahující tatáž data. Cache ve filesystému je možno vypnout (odstranit UFS_DIRHASH v konfiguračním souboru kompilace jádra), neboť je zbytečná.

Stránková cache

S buffery se pracuje tak, že pokud kód chce přečíst data z disku, zavolá bread, jádro data někam načte a vrátí na ně pointer (nebo vrátí pointer na už načtená data, pokud jsou v bufferové cachi). Tento způsob práce minimalizuje kopírování dat, pokud jsou už nacachovaná. Nevýhoda spočívá v tom, že sama bufferová cache si určuje, kam data umístí. Pokud máme soubor namapovaný pomocí mmap (nebo spuštěný program — spouštění programů se taktéž dělá pomocí mmap), tak je třeba, aby určité bloky byly nataženy v jedné stránce, aby se snadno daly namapovat do uživatelského adresního prostoru. Proto byla zavedena další cache —page cache. Page cache se používá pro stránky obsahující data souborů. Page cache je hashová tabulka, ve které je možno pomocí dvojice (inoda resp. vnoda, offset stránky) vyhledat stránku náležející danému souboru.

Původní Unix neměl virtuální paměť, a proto neměl ani page cache. Měl pouze bufferovou cache. Když byla virtuální paměť do BSD Unixu připsána, byla page cache zcela oddělená od bufferové cache. Při natahování mmapovaných stránek se data nejdříve načetla do bufferové cache a odtud se zkopírovala do stránek. OpenBSD, OS/2 a mnohé komerční Unixy to tak mají dodnes. Toto kopírování stránek je zcela zbytečné a způsobuje zpomalení. Aby se kopírování dat zabránilo, tak se page cache a buffer cache prolínají. Pokud se mají načíst nějaká data souboru do stránky, alokuje se stránka, k této stránce se alokuje příslušný počet bufferových hlav (na Linuxu struct buffer_head, na FreeBSD struct buf) a datová oblast těchto bufferů se nechá ukazovat na části stránky. Poté se buffery předají ovladači pro blokové zařízení, aby načetl data. Tento přístup zabraňuje kopírování dat, ale vede k další nepříjemnosti — spoustě práce s bufferovými hlavami. V podstatě to vypadá tak, že se při čtení několika stránek alokuje bufferová hlava pro každý blok, pak se pro každou tuto hlavu zavolá funkce čtení bufferu, tato funkce začne vyrábět požadavky na blokové zařízení a zjistí, že buffery ukazují na souvislou část disku, a tak je spojí do jednoho velkého požadavku. Rozdělování na jednotlivé bufferové hlavy a jejich spojování je zcela zbytečné.

V Linuxu 2.6 byl tento problém vyřešen — byl zaveden zcela nový model posílání požadavků na bloková zařízení — pomocí struct bio je možno poslat jeden požadavek na několik (až 16) v paměti nesouvislých stránek. V souboru mpage.c je vidět alokace stránek a jejich čtení nebo zápis pomocí struct bio. Pokud jsou data souboru na disku nesouvislá, tak se tento model nepoužívá a používají se staré bufferové hlavy. Na FreeBSD tento problém není tak veliký, neboť FreeBSD se většinou používá s velikostí bloku větší než stránka.

Direct IO

Cache byla vytvořena proto, aby urychlovala přístup k datům. Existují však situace, kdy je cache nežádoucí a naopak přístup zpomaluje. Cache je nežádoucí ve dvou případech: u aplikací pracujících s proudem velkého množství dat (například digitální video), kde se všechna data do paměti stejně nevejdou a při sekvenčním přístupu se z cache žádná data číst nebudou. Druhým případem, kde je cachování nežádoucí, jsou databázové aplikace — databázové servery dělají vlastní cachování, které je efektivnější než systémová cache, neboť databázový server zná strukturu dat a umí lépe předpovídat, ke kterým datům se bude přistupovat. Data není třeba cachovat dvakrát — jednou na úrovni databázového serveru a podruhé na úrovni operačního systému.

Direct IO je způsob, jak dělat čtení nebo zápis dat bez použití cache. Cílem direct IO je nepoužívat paměť pro cachování dat, která stejně nemá smysl cachovat, a také zabránit kopírování dat ze systémové cache do uživatelského adresního prostoru procesu. Při direct IO jsou data přenášena přímo mezi diskem a adresním prostorem procesu, který zavolal read nebo write. Pokud uživatel nastaví příznak O_DIRECT v syscallu open, budou všechny čtení a zápisy na daném souboru dělány pomocí direct IO.

Poslední verze Linuxu 2.4 pod­porují direct IO. Direct IO je implementováno pomocí tzv. kiobufů. struct kiobuf je struktura popisující stránky zamčené v adresním prostoru procesu. Stránky je možno zamknout pomocí funkce int map_user_kiobuf(int rw, struct kiobuf *buf, unsigned long va, size_t len). Funkce zamkne v paměti stránky v daném rozsahu (případně je naswapuje, pokud jsou odswapované). Odemčení stránek dělá funkce void unmap_kiobuf(struct kiobuf *buf). Direct IO na Linuxu tenhle mechanismus používá k zamčení stránek a k provedení přímého čtení nebo zápisu do adresního prostoru procesu. Andrea Arcangeli změřil, že direct IO způsobí, že čtení dat spotřebuje desetkrát méně CPU času než čtení bez direct IO. Čtení bez direct IO je tak pomalé proto, že se data nejprve načtou do systémové cache a teprve poté se kopírují do adresního prostoru procesu.

FreeBSD ve verzi 4 i 5 má také direct IO, ale pouze pro čtení. Pro zápis se používají standardní buffery. Direct IO tam funguje tak, že se zakáže swapování na celém procesu, pak se vytvoří buffer, jehož datová oblast ukazuje do userspace, stránky se naswapují a buffer se předá ovladači blokového zařízení.

Našli jste v článku chybu?

2. 1. 2004 22:08

Mikuláš Patočka (neregistrovaný)

Zda je velký globální hash nebo více lokálních hashů, je jedno (pokud nám nejde o bránění se DoS-útoku založeném na stresování jedné hashové hodnoty, ale to u filesystému nemá význam). Dokonce bych řekl, že globální hashování má v průměrném případě lepší rozložení a méně kolizí --- ale zase v nejhorším případě je globální hashování horší než lokální.

Ten UFS dirhash skutečně pomůže, ale pouze jednou --- při prvním otvírání všech souborů v adresáři se nebude muset pro každý soubor celý adresář…

2. 1. 2004 21:57

Mikuláš Patočka (neregistrovaný)

Podle mě te vícenásobný mount je stejně pitomost (máme přece symlinky). Taky nechápu, proč to kvůli němu tak zprasili ... Linux 2.2 to ještě měl jednoduše --- všude předával pouze dentry a vícenásobný mount neměl.

Vitalia.cz: Vychytané vály a válečky na vánoční cukroví

Vychytané vály a válečky na vánoční cukroví

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

Vitalia.cz: Proč vás každý zubař posílá na dentální hygienu

Proč vás každý zubař posílá na dentální hygienu

120na80.cz: 5 nejčastějších mýtů o kondomech

5 nejčastějších mýtů o kondomech

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

DigiZone.cz: Flix TV: dva set-top boxy za korunu

Flix TV: dva set-top boxy za korunu

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Vitalia.cz: Spor o mortadelu: podle Lidlu falšovaná nebyla

Spor o mortadelu: podle Lidlu falšovaná nebyla

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Vitalia.cz: Potvrzeno: Pobyt v lese je skvělý na imunitu

Potvrzeno: Pobyt v lese je skvělý na imunitu

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?