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

Zajišťování konzistence filesystému v případě výpadku

Pro zvýšení výkonu mají filesystémy asynchronní zápis — tj. data nezapisují na disk okamžitě, ale drží si je v bufferové cachi a počkají, než se nakumuluje dostatečné množství dat nebo než uplyne nějaká dlouhá doba (typicky v řádu desítek sekund až minut; je možno to v systému nastavit) — teprve pak zapíší. Po výpadku proudu nebo pádu operačního systému se filesystém nachází v nekonzistentním stavu. Některé sektory byly zapsány, některé nebyly, a pokud bychom s takovým filesystémem pracovali, docházelo by k závažným chybám (například jestliže byl zapsán soubor, ale nebyla ještě zasána bitmapa alokovaných bloků, bude soubor sice existovat a obsahovat data, ale v náhodný okamžik bude přepsán jiným souborem). Pokud se při startu filesystém nachází v nekonzistentním stavu, bude automaticky zkontrolován programem fsck, který nekonzistence opraví. To s sebou přináší problémy:

• Je to značně pomalé. Běžně to trvá několik minut; na velkých discích s mnoha malými soubory to může být až několik hodin.
• I když program fsck zkontroluje a do konzistentního stavu uvede všechny řídící struktury, nemůže do konzistentního stavu uvést samotná data, neboť neví, jaká data soubory mohou obsahovat. Kromě nesmyslných dat v souborech to přináší i ohrožení bezpečnosti systému. Představme si situaci, kdy uživatel 1 vyrobí soubor, uloží do něj svoje tajná data a pak soubor smaže. Uživatel 2 vyrobí soubor, filesystém umístí soubor na stejné místo, kde byl soubor uživatele 1. K přerušení proudu dojde v okamžiku, kdy byly zapsány alokační informace souboru, ale nebyla ještě zapsána samotná data. Po novém startu a provedení kontroly filesytému bude uživatel 2 ve svém souboru vidět tajná data uživatele 1. Tato chyba se dá zneužít i úmyslně, stačí, když útočník vyrobí soubor tak velký, aby ho jádro ještě nezačalo zapisovat, pak počká, než se zapíšou řídící informace, ale dokud se ještě nezapíšou data, vypne proud nebo shodí systém. Po novém startu systému může útočník číst data, která mu nepatří.

Používají se následující metody, které zaručují vyšší konzistenci dat:

• Synchronní zápis — nejstarší a nejsnadněji implementovatelná metoda. Umí ji Linux i FreeBSD. Data se na disk fyzicky zapisují okamžitě v systémových voláních write, mkdir apod. Vede to bohužel k několikanásobnému zpomalení diskových operací, proto se tato metoda téměř nepoužívá. Synchronní zápis může vést k nekonzistentnímu stavu filesystému, nicméně tento nekonzistentní stav nezpůsobí žádné ztráty dat. Je možné, že se budou na filesystému objevovat ztracené bloky či inody, ale není možná situace, kdy soubor bude existovat, ale nebude zapsán v bitmapě, což by vedlo k náhodnému přepsání souboru. Ztracené bloky a inody je možno uvolnit zkontrolováním celého filesystému pomocí fsck. Synchronní zápis v Linuxu ani FreeBSD nezaručuje bezpečnost dat —v případě pádu v nevhodnou dobu může uživatel číst data, která mu nenáleží. Synchronní zápis by bylo možno implementovat tak, aby bezpečnost dat zaručoval, ale v Linuxu ani FreeBSD tomu tak není.

• Soft updates — metoda implementovaná pouze na FreeBSD. Bufferová cache obsahuje závislosti mezi jednotlivými buffery — závislost je toho typu, že buffer X musí být zapsán dříve než buffer Y. Kernel thread starající se o zápis modifikovaných bufferů zapisuje buffery tak, aby tyto závislosti nebyly porušeny. Kód filesystému vždy při značení špinavých bufferů popisuje, jaké závislosti mezi nimi jsou. Například při vytváření souboru je řečeno, že položka v adresáři musí být zapsána později než inoda a že položka v adresáři musí být zapsána později než bitmapa inod. Tím se zajistí, že ať systém spadne v jakémkoli okamžiku, bude adresář konzistentní. Sice může vzniknout ztracená inoda, na kterou nikdo neukazuje, ale nemůže vzniknout situace, kdy adresář ukazuje na nesmyslnou inodu. Při zápisu dat do souboru se rovněž vytvářejí tato pravidla: ukazatel na blok musí být zapsán později než data v tomto bloku a ukazatel na blok musí být zapsán později než bitmapa. Může tedy vzniknout ztracený blok, ale nemůže vzniknout ukazatel na nealokovaný blok nebo ukazatel na blok obsahující náhodná data. Bezpečnost filesystému tedy je zajištěna.

  Filesystém musí zvlášť dávat pozor na cyklické závislosti. Například pokud je přesunut soubor z adresáře A do adresáře B, vznikne závislost, že adresář A je třeba zapsat dříve než adresář B (neboť ztracený soubor je menší škoda než soubor s refcount 1, na který se odkazují dva adresáře). Pokud je přesunut další soubor z adresáře B do adresáře A, vznikne opačná závislost: adresář B je třeba zapsat dříve než adresář A. Kód musí tuto situaci detekovat, a pokud nastane, tak buffer obsahující A zdvo­jit, původní kopii znepřístupnit pro vyšší vrstvy, do nové kopie nechat zapisovat změny a vyrobit závislost říkající, že: nejdříve se zapíše původní buffer adresáře A, pak se zapíše buffer adresáře B a pak se zapíše nový buffer adresáře A.

• Žurnálování — Žurnálování je metoda, která umožňuje udržet po výpadku proudu zcela konzistentní stav filesystému. Není třeba provádět kontrolu filesystému a nevznikají ztracené bloky nebo inody jako u soft updates. Na filesystému je vyčleněna oblast (veliká obvykle pár megabytů) nazývaná žurnál. Ovladač filesystému musí změny provádět v tzv. transakcích. Transakce je sada několika modifikací dat, která převádí filesystém z jednoho konzistentního stavu do druhého konzistentního stavu. Například při vytváření souboru se vyrobí transakce, do které náležejí následující operace: zapsání položky adresáře, zapsání inody, zapsání bitu v bitmapě alokovaných inod, zmenšení počítadla volných inod v superbloku. Operace náležející transakci se nezapisují na disk, ale nejdříve se zapisují do žurnálu. Až je celá transakce v žurnálu zapsaná, zapíše se do něj speciální značka — commit transakce. Poté se buffery obsahující jednotlivé modifikace mohou zapisovat na disk jako při asynchronním zápisu. Do žurnálu se zpravidla zapisuje pořád dopředu, a když dojde k jeho zaplnění, začne se zapisovat opět od začátku (při této operaci je třeba zapsat na příslušná místa na disku všechny buffery obsahující modifikovaná data). Při mountu filesystému se kontroluje žurnál. Pokud je v něm nalezena transakce včetně commit značky, tak se všechny operace náležející této transakci zapíší na příslušná místa na disku. Pokud je v žurnálu nalezena neúplná transakce bez commitu, ignoruje se.

  Žurnálování zajišťuje absolutní konzistenci filesystému po výpadku. Pokud počítač spadl během zápisu transakce do žurnálu, je transakce v žurnálu neúplná a bude při příštím startu ignorována. V takovém případě máme garantováno, že ještě nedošlo k zápisu žádných dat na disk mimo žurnál. Pokud celý zápis transakce do žurnálu proběhl (včetně commit značky) a počítač spadl během zápisu dat na disk, bude při příštím startu celá transakce z žurnálu rekonstruována, čímž budou nekompletní data na disku přepsána. Ať spadne počítač v jakémkoli okamžiku, data budou konzistentní. Aby žurnálování mohlo správně fungovat, předpokládá se, že disk je schopen provést tzv. atomický zápis sektoru — tj. v sektoru se po výpadku budou nacházet buď úplná stará, nebo úplná nová data. Pokud dojde k výpadku proudu během zápisu sektoru, disk musí být schopen tento zápis dokončit. Současné disky to umějí. Schopnost atomického zápisu sektoru nemají například diskety (pokud disketovou mechaniku vypnete během zápisu dat, výsledkem bude neúplně zapsaný sektor, který nejspíše bude produkovat CRC chybu), proto používání žurnálového filesystému na disketách nemá smysl.

  Do žurnálu se zpravidla zapisují pouze metadata (tj. řídící informace filesystému) a nikoli samotná data obsažená v souborech. Důvodem je rychlost — při žurnálování je potřeba na disk zapsat dvakrát více dat než při normálním zápisu a zapisování celých souborů by proces zápisu dvakrát zpomalilo. Pokud se data do žurnálu nezapisují, je třeba zajistit jejich konzistenci, aby nevznikl výše popsaný bezpečnostní problém: metadata jsou zapsaná, data nejsou zapsaná, uživatel po pádu bude moci číst cizí smazané soubory. Obecně platí, že před zapsáním commit značky je potřeba zapsat všechna nově vzniklá data. Musí se také udržovat konzistence mezi datovými a metadatovými buffery, což logiku bufferové cache komplikuje (například není možné zapsat data do bloku, ve kterém dříve byla metadata, je-li v žurnálu ještě nějaká transakce pracující s těmito metadaty).

  Neexistuje žurnálový filesystém pro FreeBSD. Pro Linux existuje několik žurnálových filesystémů:

  Ext3 — tento filesystém má zcela shodnou strukturu s filesystémem Ext2 až na to, že provádí žurnálování. Existující filesystém Ext2 je možno přetvořit na Ext3 pouhým přidáním speciálního souboru obsahujícího žurnál. Ext3 je možno zpětně namountovat jako Ext2 (v takovém případě se neprovede obnovení žurnálu — proto před tím nesmělo dojít k pádu). Ext3 může pracovat ve třech režimech: Unordered data — nebude udržováno pořadí mezi daty a metadaty, takže zde existuje bezpečnostní problém;Ordered data — bude zajištěno, že data budou zapsána dříve než commit transakce, takže je filesystém bezpečný; Journal data — data budou zapisována do žurnálu. To dvakrát zpomalí rychlost zápisu dat, ale způsobí, že bude udržováno i pořadí jednotlivých volání funkce write. Doporučená metoda je ordered data, což zajišťuje bezpečnost a nezpomaluje tolik jako žurnálovaná data.

  Ext3 se nachází v jádrech 2.4 i 2.6 (je možno stáhnout patch Ext3 i pro jádra 2.2), ale z komentářů v kódu je vidět, že ještě úplně odladěný není — může se vyskytovat špatné předpovídání velikosti transakce, což může vést k přeplnění žurnálu, synchronizace metadat a dat také není absolutně v pořádku. Tyto chyby se v běžných případech moc nevyskytují.

  ReiserFS — tento filesystém původně nebyl žurnálovaný; žurnál byl do něho dodělán až později. ReiserFS nezaručuje pořadí zápisu dat a metadat (a z kódu je patrné, že programátoři na tento problém vůbec nepomýšleli), proto na něm existuje bezpečnostní problém.

  JFS — tento filesystém byl vyvinut firmou IBM a je používán na jejích operačních systémech AIX a OS/2. Jeho kód byl uvolněn pod GNU General Public License a zařazen do experimentálního Linuxu 2.6. Vzhle­dem k tomu, že se nachází pouze v experimentálních jádrech, není vhodný pro běžné použití. Bezpečnostní problém s pořadím zápisu dat a metadat se tam programátoři snažili řešit, ale v současné verzi to nefunguje. Dá se předpokládat, že před vydáním stabilního jádra bude tento problém opraven.

  XFS — filesystém vyvinutý firmou SGI pro systém IRIX. Jeho nepříjemností je, že kód je stále psán pro rozhraní VFS IRIXu a nad sebou obsahuje vrstvu, která Linuxová volání překládá na IRIXová (která jsou podobná BSD).

  U všech čtyřech žurnálovaných filesystémů pro Linux je jejich hlavní nevýhodou značná velikost a komplikovanost kódu. Linuxová bufferová cache nebyla na žurnálování nikdy stavěná, a tak je implementace žurnálu dost složitá — například je velmi obtížné bufferové cachi sdělit, že buffer nesmí zapsat dříve než obsah žurnálu, případně že stránky souboru musí zapsat dříve, než dojde ke commitu transakce popisující vytvoření souboru. Díky tomu se v žurnálových filesystémech notoricky vyskytují bugy, které jsou většinou řešeny pravděpodobnostním způsobem (sám jsem na kernel mailing listu četl odpověď nějakého vývojáře ext3 na bug report o deadlocku: „v 2.4.18 jsme měli několik deadlocků, v 2.4.23 máme stále ještě jeden, ale tohle vypadá jinak, ještě se na to podívám”).

  U komerčních filesystémů je navíc značnou nevýhodou jejich ohromná velikost, z čehož plyne nemožnost kontrolovat kód nezávislými lidmi. Pokud člověk sám píše filesystém, tak raději bude několik týdnů přemýšlet, jak to udělat jednoduše, než aby se pustil do něčeho složitého. V komerčním prostředí, kde člověk, co filesystém navrhuje, má pod sebou neomezené množství programátorů, kteří to budou programovat, není žádná motivace držet kód malý a jednoduchý.

• Existují i další metody, které zajišťují podobnou funkčnost jako žurnálování, ale jejich princip fungování je zcela jiný. Existují pouze v experimentálních filesystémech, do jádra se nedostaly.
• Fázový strom — na filesystém je možno pohlížet jako na strom ukazatelů: superblok ukazuje na kořenový adresář a na bitmapy, adresář ukazuje na inody, inody ukazují na podadresáře a tak dál. Metoda fázového stromu funguje tak, že všechny zápisy se dělají na nealokovaná místa na disku. Proto tyto zápisy nemohou ohrozit konzistenci dat. Když se například má zapsat inoda, zapíše se na místo, které je v bitmapě inod nealokované. Pak se na další nealokované místo zapíše adresář, ve kterém se inoda nacházela (a v tomto adresáři se modifikuje ukazatel na inodu na její nové místo). Pak se opět na nealokované místo zapíše inoda toho adresáře, její nadadresář a tak dále až ke kořeni. Na nealokovaná místa se zapíší i nové bitmapy, které tyto změny popisují. Nakonec se zapíše superblok s novým ukazatelem na nový kořenový adresář a na nové bitmapy, čímž se během jedné operace zápisu filesystém dostane z jednoho konzistentního stavu do druhého. Tato metoda vede k zápisu značného množství dat, je pomalá, a proto se moc nepoužívá.
• Crash counts — filesystém má počítadlo pádů (o velikosti například 16 bitů) a tabulku, kde pro každou hodnotu počítadla pádů je počítadlo transakcí. Po mountu filesystém na disku zvýší počítadlo pádů o 1 (ale v paměti si nechá staré), načte tabulku počtu transakcí a v paměti (na disk nezapisuje) zvýší o jedna hodnotu na pozici počítadla pádů. Při odmountování filesystému je počítadlo pádů na disku opět zmenšeno o 1. Každý pointer na disku má kromě adresy dvě položky — crash count ( cc) a transaction count ( txc). Pointer je platný, pokud crash_count_table[cc] - txc >= 0. Když filesystém zapisuje nějaká metadata, zapisuje k pointerům aktuální crash count a transaction count. Pokud systém spadne, bude při dalším startu pracovat s crash count větším o 1 (načteným z disku) a všechny pointery vyrobené do doby pádu budou považovány za neplatné. Když se zapíše tabulka počítadel transakcí na disk, začnou být náhle všechny dříve zapsané pointery platné. Pak se v paměti zvýší počítadlo transakcí o 1 a mohou se zapisovat nová data. Některé struktury, které nemají povahu pointerů (např. bitmapy), je nutno na disku ukládat dvakrát a pro tuto dvojici mít cc  a

  txc určující, která z bitmap je platná. Při zápisu do bitmapy se zkontroluje, zda cc a txc bitmapy jsou aktuální hodnoty, se kterými se pracuje — pokud ano, zápis se provede (a v případě pádu bude platná ta druhá bitmapa, do které se nezapisovalo). V případě, že cc a  txc

  bitmapy nejsou aktuální, musí dojít ke zkopírování platné bitmapy do druhé a k nastavení cc a txc dané dvojice bitmap na aktuální hodnoty. Tato metoda má tu nevýhodu, že umožňuje přežít pouze pevný počet pádů (v případě 16bitového crash count je to 65536) — až crash count dojde na horní hranici, je třeba stejně celý filesystém projít, zkontrolovat, vymazat neplatné pointery a crash count vrátit zpátky na nulu.

Nedostatky unixového filesystému

Unixový filesystém vznikl před více než 30 lety, a proto má některé nedostatky, které se v novějších filesystémech podařilo odstranit.

• Předalokované místo na inody — je zbytečné umisťovat inody pouze na pevná předalokovaná místa. Volné inody pak buď zabírají zbytečně mnoho místa, nebo dochází k opačnému jevu, kdy inody docházejí. Lepší filesystémy jsou schopny alokovat inody kdekoli na disku.
• Popis alokace souboru pomocí přímých a nepřímých bloků — tato metoda umožňuje vyhledat libovolnou část souboru v konstantním čase (na rozdíl třeba od FAT filesystému, kde k nalezení konce souboru je třeba sekvenčně projít ukazatele na všechny jeho bloky). Nepřímé bloky však zabírají spoustu místa, jejich čtení zabírá čas, a i když máme přístup k libovolné části souboru v konstantním čase, k tomuto přístupu potřebujeme až tři přístupy na disk. Lepší je využít předpokladu, že fragmentace souborů je malá, a alokační informace ukládat do dvojic (blok na disku, počet souvislých bloků). Tyto dvojice je pak možno skládat do b-stromu, lineárního seznamu (z hlediska teoretické informatiky je lineární seznam špatný, nicméně vzhledem k tomu, že soubory moc zfragmentované nebývají, není tato struktura špatná) nebo na ně ukazovat indirect bloky různé úrovně.
• Adresáře jako lineární seznamy — vyhledávání v nich je pomalé, pokud adresář obsahuje spoustu souborů. Některé filesystémy ukládají adresáře do b-stromu, takže jsou schopny libovolný soubor nalézt v logaritmickém ča­se.
• Informace jsou v inodách a ne v adresáři — pokud na Unixu napíšeme ls -la, bude tato operace trvat poměrně dlouho, protože se pro každý soubor adresáře bude muset přečíst jeho inoda. Některé filesystémy mají informaci o souborech uloženou rovnou v adresářových položkách, takže daná operace na nich bude trvat výrazně kratší dobu. Pokud jsou informace o souboru v adresářových položkách, neumožňuje to použít hardlinky; na druhou stranu uživatelé hardlinky moc často nepoužívají a používají mnohem raději symlinky, neboť hardlinky nejsou vidět ve výpisech adresáře a vedou ke zmatenosti uživatele.

Existují novější filesystémy, které se tyto problémy snaží nějak řešit. Na FreeBSD není v současné době jiný použitelný diskový filesystém než UFS. Na Linuxu existují kromě původního filesystému Ext2 i alternativy:

• Ext3 — tento filesystém má zcela stejnou strukturu jako Ext2. Ext3 se nachází v jádrech 2.4 a 2­.6. Vylepšením oproti Ext2 je žurnálování a možnost vyhledávat v adresářích s použitím hashovaného stromu. Jméno souboru je zahashováno, podle hodnoty se projde strom a najde místo, kde je uložena adresářová položka. Strom je uložen v samotných blocích adresáře, které obsahují prázné položky, takže předchozí verze filesystému mohou tento adresář číst nebo dokonce na něj i zapisovat (čímž ovšem strom zničí a bude se muset použít sekvenční vyhledávání).
• ReiserFS — Filesystém ReiserFS je optimalizován pro ukládání malých souborů. Filesystém ukládá do stromu nejen obsah adresáře, ale i jednotlivé inody a malé soubory. Dokáže do jednoho bloku uložit několik malých souborů, proto je vhodný na proxy cache, news nebo mail servery, či jiné aplikace, které potřebují pracovat s velkým množstvím malých souborů. Na druhou stranu, prohledávání stromu při vyhledávání inody zpomaluje, proto je tento filesystém při některých typech zátěže pomalejší než Ext2.
• JFS a XFS — Tyto filesystémy mají adresáře ve tvaru stromu, popis bloků náležících souboru rovněž ve tvaru stromu a mají dynamicky alokované místo na inody.

Další filesystémy v jádrech

Na Linuxu existuje i větší množství dalších filesystémů, které byly napsány kvůli kompatibilitě s jinými operačními systémy. Často k nim chybí potřebné programy pro vytvoření a zkontrolování filesystému a nemá smysl je používat, pokud nemáme na stejném počítači jiný operační systém, který je vyžaduje. Patří sem ADFS (Acorn disk file system — nativní filesystém systému RiscOS), AFFS (Amiga fast file system), BFS (UnixWare boot file system), EFS (filesystém starších systémů IRIX), FAT (filesystém DOSu a Windows 95/98/ME), HFS (filesystém na Macintoshi), HPFS (High-performance file system — filesystém používaný systémem OS/2), ISOFS (filesystém na CD), JFFS (Journaled flash file system — filesystém optimalizovaný na flash karty místo na disky), Minix (filesystém dnes již historického operačního systému Minix), NTFS (filesystém Windows NT/2000/XP, podpora v Linuxu je read-only), QNX4 (filesystém operačního systému QNX, v Linuxu read-only), SYSV (filesystém používaný na komerčních Unixech Xenix, SCO a Coherent), UDF (nový filesystém na CD), UFS (rodina filesystémů používaná na FreeBSD, NetBSD, OpenBSD, SunOS, NeXTstep; na některé typy tohoto filesystému Linux umožňuje zapisovat, na jiné ne), VXFS (nativní filesystém UnixWare; na Linuxu read-only).

Na FreeBSD je množství cizích filesystémů výrazně menší — FreeBSD podporuje FAT, Ext2 (čtení i zápis, ale ve spoustě verzí FreeBSD dost zabugovaný, kdysi mi to zničilo jeden blok v tabulce inod), HPFS (read-only), ISOFS, NTFS (read-only), UDF.