Sjednocující souborové systémy: Implementace, část 1.

27. 5. 2009 | Jirka Bourek

Články - Sjednocující souborové systémy: Implementace, část 1.  

Tento týden popíšeme několik implementací sjednocujících souborových systémů v technických detailech. V tomto článku jsou popsány sjednocené adresáře Plan9, sjednocující připojení v BSD a sjednocující připojení v Linuxu.

Originál tohoto článku napsala Valerie Aurora (dříve Henson), vyšel na LWN.net.

V minulém článku jsme probrali možnosti nasazení, základní koncepty a běžné návrhové problémy sjednocujících [union mount] souborových systémů. Příští článek pokryje unionfs, aufs, možná jeden nebo dva další sjednocující souborové systémy a sérii uzavře.

Pro každý souborový systém popíšeme jeho základní architekturu, vlastnosti a implementaci. Část o implementaci se zaměří na vybělení [whiteouts] a čtení adresářů. Shrnutí se bude týkat aspektů návrhu softwaru u každé implementace, tj. velikosti a složitosti kódu, invazivnosti a břemene naloženého vývojářům souborových systémů.

Před přečtením tohoto článku si možná budete chtít prohlédnout právě vydané poznámky z Union mount workshop, který se konal loni v listopadu. Je to dobré shrnutí vlastností, které jsou pro vývojáře distribucí nejnaléhavější. Z úvodu: Všechny důvody nasazení, které nás zajímají, se v podstatě zužují na stejnou věc: Mít obraz nebo souborový systém, který se používá v režimu pouze pro čtení (buď protože není zapisovatelný, nebo protože zápis není žádoucí), a předstírat, že je zapisovatelný, přičemž změny se ukládají někde jinde.

Sjednocující adresáře Plan9

Operační systém Plan9 (zdrojový kód lze prohlížet zde) implementuje sjednocování svým zvláštním Plan 9 způsobem. Ve sjednocujících adresářích Plan 9 se spojuje jenom adresář nejvyšší úrovně, podadresáře ne. Protože není omezován standardy UNIXu, neimplementuje tento operační systém vybělení a ani neodstraňuje duplicitní záznamy - pokud se na obou souborových systémech vyskytuje soubor stejného jména, prostě je ve výpisu adresáře vrácen dvakrát.

Sjednocující adresář Plan 9 se vytvoří takto:

bind -a /home/val/bin/ /bin

To způsobí, že adresář /home/val/bin je připojen "za" (volba -a [after]) /bin; další volby jsou vložit nový adresář před [before] existující adresář nebo existující adresář úplně nahradit. (Toto řazení přijde autorce článku podivné, protože chce, aby příkazy v jejím osobním bin/ měly přednost před příkazy systémovými, ale je to příklad z dokumentace Plan 9.) Brian Kernighan vysvětluje možnosti využití sjednocených adresářů: Mechanismus sjednocených adresářů nahrazuje seznam cest k prohledání [search path] konvenčních UNIXových příkazových řádků. Z vašeho pohledu jsou všechny spustitelné programy v /bin. Sjednocující adresáře mohou teoreticky nahradit mnoho využití základních UNIXových stavebních bloků, kterými jsou symbolické odkazy a cesta pro prohledávání.

Bez vybělení a odstranění duplikátů je triviální implementovat readdir() nad sjednocenými adresáři. Posun [offset] záznamu v adresáři souborového systému pod ním odpovídá posunu záznamu v adresáři od začátku adresáře. Sjednocující adresáře se chovají tak, jako by obsah adresářů pod nimi byl spojen dohromady.

Plan 9 implementuje alternativu k readdir(), kterou stojí za to zmínit - dirread(). dirread() vrací strukturu Dir popsanou v man stránce stat(). Důležitou částí Dir je členská proměnná Qid. Qid je:

...struktura obsahující pole path a vers: Je garantováno, že path je unikátní mezi všemi jmény cest, kterou jsou v současnosti k dispozici na souborovém serveru, vers se mění pokaždé, když je soubor změněn. path je long long (64 bitů, vlong) a vers je unsigned long (32 bitů, ulong).

Proč je to tedy tak zajímavé? Jedním z důvodů, proč je tak obtížné implementovat readdir(), je, že vrací pouze členskou proměnnou d_off ze struct dirent; její typ je off_t (32 bitů, pokud aplikace nebyla přeložena s podporou velkých souborů), které označuje záznam v adresáři, kde má aplikace pokračovat ve čtení při dalším volání readdir. To funguje dobře, dokud je d_off jednoduchý offset v bytech v plochém souboru menším než 2³² bytů a existující záznamy v adresáři se nikdy nepřesouvají - což neplatí pro mnohé moderní souborové systémy (XFS, btrfs, ext3 s htree indexy). 96bitové Qid je mnohem lepší ukazatel než 32 nebo 64bitové off_t. Dobré shrnutí problémů spojených s implementací readdir() si můžete přečíst v excelentním příspěvku Theodora Y. Ts'o na toto téma v mailové konferenci btrfs.

Z pohledu návrhu softwaru jsou sjednocující adresáře Plan 9 nebe na zemi. Bez vybělení, odstraňování duplikátních záznamů v adresáři, komplikací s posunem v adresáři a slučování jmenných prostorů pod nejvyšším adresářem je implementace jednoduchá a snadno udržovatelná. Praktická implementace sjednocujících souborových systémů pro Linux (nebo jiný UNIX) by tyto problémy musela vyřešit. Pro naše účely slouží sjednocující adresáře Plan 9 hlavně jako inspirace.

Sjednocující spojení BSD

BSD implementuje dvě formy sjednocování: Volbu -o union příkazu mount, která vytvoří spojené adresáře podobné těm v Plan 9, a příkaz mount_unionfs, který implementuje sjednocující systémy s více vlastnostmi, s vybělením a spojováním celého jmenného prostoru. Zaměříme se na ten druhý.

V toto článku se pro specifické implementační detaily používají dva zdroje: Původní implementace sjednocujících připojení, která je popsána v příspěvku z 1995 USENIX Sjednocující připojení v 4.4BSD-Lite [PS], man stránku mount_unionfs z FreeBSD 7.1 a zdrojový kód. U ostatních BSD mohou být odlišnosti.

Adresář lze sjednoceně připojit "pod" nebo "nad" existující adresář nebo sjednocující připojení, pokud je nejvyšší větev zapisovatelného spojení zapisovatelná. Jsou podporovány dva režimy vybělení: Buď je vybělení vždy vytvořeno, když je odstraněn adresář, nebo se vytváří pouze v případě, když ve větvi pod zapisovatelnou aktuálně existuje záznam v adresáři stejného jména. Jsou podporovány tři režimy pro nastavování vlastnictví a práv souborů kopírovaných výše. Nejjednodušší je transparent, ve kterém si soubory ponechávají stejného vlastníka a práva jako originál. Režim masquerade umožňuje, aby soubory zkopírované výše vlastnil konkrétní uživatel, a podporuje sadu připojovacích voleb určujících nová práva souboru. Režim traditional nastavuje vlastníka na uživatele, který spustil příkaz pro sjednocující připojení, a práva nastavuje podle umask v čase připojení.

Když je otevřen adresář, vytvoří se adresář stejného jména v nejvyšší zapisovatelné vrstvě, pokud již neexistuje. Z pojednání:

Vytvořením stínových adresářů agresivně během prohledávání se sjednocující souborový systém vyhýbá nutnosti hledat a možná vytvářet řetěz adresářů od kořene spojení k bodu kopírování výše. Vzhledem k tomu, že adresář spotřebovává zanedbatelné místo na disku, vytváření adresářů, když jsou poprvé procházeny, se zdá být lepší alternativou.

Výsledkem je, že find /sjednoceni vyústí v kopírování každého adresáře (ale ne záznamů v adresáři, které ukazují na ne-adresáře) do zapisovatelné vrstvy. Pro většinu obrazů souborových systémů to spotřebuje zanedbatelné množství místa (méně než například prostor rezervovaný pro uživatele root nebo spotřebovaný nevyužitými inody v souborovém systému stylu FFS.)

Soubor se kopíruje nahoru do nejvyšší vrstvy, když je otevřen s právem k zapisování nebo když se mění jeho atributy. (Vzhledem k tomu, že adresáře se kopírují při otevření, je garantováno, že adresář na zapisovatelné vrstvě již existuje.) Jestliže má soubor, který má být kopírován, několik pevných odkazů [hard link], jsou ostatní ignorovány a nový soubor má počet odkazů 1. To může rozbít programy, které používají pevné odkazy a očekávají, že změna přes jeden odkaz se projeví při odkazu přes jiný odkaz. Takové aplikace nejsou příliš běžné, ale nikdo neprovedl systematickou studii, která by se zabývala tím, které aplikace v takové situaci selžou.

Vybělení jsou implementována zvláštním záznamem v adresáři, DH_WHT. Vybělené záznamy v adresáři se neodkazují na žádný skutečný inode, ale pro jednoduchou kompatibilitu s existujícími nástroji pro souborové systémy jako fsck obsahuje každý záznam pro vybělený adresář číslo inodu (WINO - číslo inodu rezervované pro vybělení). Souborový systém, nad kterým operace probíhají, musí být modifikován tak, aby podporoval záznam typu vybělený adresář. Nové adresáře, které nahrazují vybělený záznam, jsou označeny jako neprůhledné novou vlastností inodu "opaque" [neprůhledný], takže prohledávání přes ně neprochází níže (což opět vyžaduje minimální podporu souborového systému níže).

Duplikátní záznamy a vybělení jsou vyřešeny implementací readdir v uživatelském prostoru. Při opendir() C knihovna přečte celý adresář najednou, odstraní duplikace, aplikuje vybělení a cachuje výsledky.

Sjednocující spojení v BSD se nepokouší řešit změny ve větvích pod zapisovatelnou nejvyšší větví (které jsou ale povoleny). Není popsáno, jak je implementováno rename().

Příklad z man stránky mount_unionfs:

Příkazy

    mount -t cd9660 -o ro /dev/cd0 /usr/src
    mount -t unionfs -o noatime /var/obj /usr/src

připojí CD-ROM mechaniku /dev/cd0 do /usr/src a poté nad ni připojí
/var/obj. Pro většinu účelů to má efekt, že strom zdrojových kódů
se zdá být zapisovatelný, přestože je uložen na CD-ROM. Volba
-o noatime je užitečná, aby se zabránilo nepotřebnému kopírování
z nižších na vyšší vrstvy.

Další příklad (autorka poznamenává, že správu zdrojových kódu je lepší implementovat mimo souborový systém):

Příkaz
    mount -t unionfs -o noatime -o below /sys $HOME/sys

připojuje systémový strom zdrojových kódů pod adresář sys
v domovském adresáři uživatele. To umožňuje jednotlivým uživatelům
vytvářet vlastní změny zdrojových kódů a překládat nová jádra bez
toho, aby se tyto změny zviditelňovaly ostatním uživatelům.

Sjednocující připojení v Linuxu

Podobně jako sjednocující připojení v BSD je linuxové sjednocování souborových systémů implementováno ve vrstvě VFS s malou podporou používaných souborových systémů pro značky vybělených a neprůhledných adresářů. Existuje několik verzí těchto patchů, napsali a upravili je mezi jinými Jan Bunck, Bharata B. Rao a Miklos Szeredi.

Jedna verze tohoto kódu spojuje pouze nejvyšší adresář, podobně jako sjednocující adresáře Plan 9 a volba -o union u BSD. Tato verze, na kterou se budeme odkazovat jako na sjednocené adresáře, je detailněji popsána v článku Goldwyna Rodriguese a v nedávno zaslané aktualizované sadě patchů Miklose Szerediho. Ve zbytku tohoto článku se zaměříme na verzi sjednocujícího připojení, která slučuje celý jmenný prostor.

Linuxová sjednocující připojení jsou v současnosti aktivně vyvíjena. Tento článek popisuje verzi vydanou Janem Blunckem proti Linuxu 2.6.25-mm1, util-linux 2.13 a e2fsprogs 1.40.2. Sadu patchů jako quilt sérii je možné stáhnout z Janova ftp serveru:

Jaderné patche: ftp://ftp.suse.com/pub/people/jblunck/patches/

Nástroje: ftp://ftp.suse.com/pub/people/jblunck/union-mount/

Autorka článku vytvořila webovou stránku s odkazy na gitové verze patchů výše a nějakou dokumentaci ve stylu HOWTO na adrese http://valerieaurora.org/union.

Sjednocující připojení se vytvoří připojením souborového systému s nastaveným příznakem MS_UNION. (V kódu mount jsou definovány příznaky MS_BEFORE, MS_AFTER a MS_REPLACE, ale v současnosti se nepoužívají.) Pokud je uveden příznak MS_UNION, pak připojený souborový systém musí být buď pouze pro čtení, nebo podporovat vybělení. V současné verzi sjednocujících připojení je příznak sjednocování nastaven volbou -o union předanou příkazu mount. Pro příklad vytvoření sjednocení dvou souborových systémů na loopback zařízeních /img/ro a /img/rw by se spustilo:

# mount -o loop,ro,union /img/ro /mnt/union/
# mount -o loop,union /img/rw /mnt/union/

Každé sjednocující připojení vytvoří struct union_mount:

struct union_mount {
    atomic_t u_count;		/* reference count */
    struct mutex u_mutex;
    struct list_head u_unions;	/* list head for d_unions */
    struct hlist_node u_hash;	/* list head for searching */
    struct hlist_node u_rhash;	/* list head for reverse searching */
    struct path u_this;		/* this is me */
    struct path u_next;		/* this is what I overlay */
};

Jak je popsáno v Documentation/filesystems/union-mounts.txt, "Všechny struktury union_mount jsou cachovány ve dvou hash tabulkách, jedné pro vyhledávání nejbližší nižší a jedné pro vyhledávání nejbližší vyšší vrstvy v zásobníku sjednocení."

Vybělení a neprůhledné adresáře jsou implementovány v podstatě stejným způsobem jako v BSD. Souborový systém pod připojením musí explicitně podporovat vybělení definováním operace .whiteout pro adresáře (v současnosti jsou vybělení implementována pouze v ext2, ext3 a tmpfs). Implementace v ext2 a ext3 používají záznam typu adresář vybělení (DT_WHT) který je definován v include/linux/fs.h již léta, ale kromě souborového systému Coda se nikde nepoužívá. Číslo rezervovaného vybělovacího inode (EXT3_WHT_INO) je definováno, ale ještě se nepoužívá; v současnosti bělící záznamy alokují normální inode. Je definován nový příznak inodu (S_OPAQUE), který značí neprůhledné adresáře. Stejně jako v BSD jsou adresáře označeny jako neprůhledné v případě, že nahrazují vybělený záznam.

Soubory jsou kopírovány výše, pokud je soubor otevřen k zápisu. Jestliže je to nutné, každý adresář v cestě k souboru je kopírován do nejvyšší větve (kopírování adresářů podle potřeby). V současnosti je kopírování výše podporováno pouze pro běžné soubory a adresáře.

readdir() je jeden z nejslabších článků současné implementace. Je implementován stejným způsobem jako v sjednocujícím připojení v BSD, ale v jádře. Pole d_off je nastaveno na offset v aktuálním adresáři mínus velikosti předchozích adresářů. Adresářové záznamy z adresářů pod nejvyšší vrstvou musí být kontrolovány proti předchozím vrstvám kvůli duplikátům a vybělením. V současné implementaci čte každé systémové volání readdir() (technicky getdents()) všechny záznamy v adresáři do jaderné cache. Potom všechny záznamy, které mají být vráceny, porovná s těmi, které jsou již v cache, předtím, než je vrátí do uživatelského bufferu. Konečným výsledkem je, že readdir() je složité, pomalé a potenciálně může alokovat velké množství jaderné paměti.

Jedním řešením je použít přístup z BSD a cachování, vybělení a zpracovávání duplikátů provádět v uživatelském prostoru. Bharata B. Rao pracuje na návrhu podpory pro readdir() sjednocujícího připojení v glibc. (Standard POSIX umožňuje, aby bylo readdir() implementováno na úrovni libc, pokud čisté jaderné systémové volání nesplňuje všechny požadavky.) To by přesunulo spotřebu paměti do aplikace a cache by bylo možné uchovávat. Dalším řešením by bylo nějakým způsobem vyřešit uchovávání jaderné cache.

Autorka článku navrhuje použít techniku ze sjednocujícího připojení v BSD a rozšířit ji: Proaktivně kopírovat nejenom adresáře, ale všechny záznamy v adresáři z nižších souborových systémů, zpracovat duplikace a vybělení, nastavit adresář jako neprůhledný a zapsat ho na disk. Efektivně by to znamenalo, že by se záznamy v adresáři pro vybělení a duplikáty zpracovaly při prvním otevření adresáře a výsledná "cache" záznamů v adresáři by se uložila na disk. Záznamy v adresáři ukazující na soubory by nějak musely oznamovat, že jsou "propadávající" [fall-through] (opak k vybělení - explicitní požadavek na vyhledání souboru na nižší vrstvě). Vedlejší efekt tohoto přístupu je, že vybělení již nejsou zapotřebí.

Jeden problém, který je potřeba s tímto přístupem vyřešit, je, jak reprezentovat položky v adresáři ukazující na souborový systém níže. Nabízí se několik řešení: Záznam by mohl ukazovat na rezervované číslo inodu, souborový systém by mohl alokovat inode pro každý záznam, ale označit ho novým atributem inodu S_LOOKOVERTHERE, mohl by vytvořit symlink na rezervovaný cíl atd. Tento přístup by spotřebovával více místa na nejvyšším souborovém systému, ale všechny ostatní přístupy vyžadují alokovat stejné množství místa v paměti a obecně je nám paměť dražší než disk.

Méně akutní záležitost současné implementace je, že čísla inodů nejsou mezi booty stabilní (vizte předchozí díl článku o sjednocující souborových systémech, kde najdete detailnější popis toho, proč je to problém). Pokud by "propadávající" adresáře byly implementovány alokováním inodu pro každý záznam v adresáři na souborovém systému níže, pak by stabilní čísla inodů byla přirozeným vedlejším efektem. Další možností je uložit někam přetrvávající mapu inodů - například v souboru v nejvyšším adresáři nebo externím souborovém systému.

Pevné odkazy [hard link] jsou řešeny - nebo přesněji neřešeny - stejným způsobem jako v sjednocujících připojení v BSD. Opět není jasné, kolik aplikací závisí na modifikaci souboru přes jeden pevný odkaz [hard link] a pozorování změn přes jiný pevný odkaz (na rozdíl od symbolického odkazu). Jediné řešení, které napadá autorku článku, jak toto vyřešit korektně, je udržovat někde na disku přetrvávající cache inodů, na které jsme narazili a měly několik pevných odkazů.

Zde je příklad, jak by to fungovalo: Řekněme, že začneme s kopírováním inodu 42 výše a zjistíme, že má počet odkazů tři. V takovém případě bychom vytvořili záznam v databázi pevných odkazů, který by obsahoval id souborového systému, číslo inodu, počet odkazů a číslo inodu nové kopie v souborovém systému nejvyšší úrovně. Bylo by ho možné vytvořit například ve formátu CSV nebo jako symbolický odkaz v rezervovaném adresáři kořenového adresáře (např. /hardlink_hack/<fs_id>/42), který by odkazoval na nové_číslo_inodu 3) nebo ve skutečné databázi. Pokaždé, když by se otevíral inode ze souborového systému níže, bychom prohledali databázi pevných odkazů; pokud by existoval záznam, snížili bychom počet odkazů a vytvořili pevný odkaz na správný inode v novém souborovém systému. Až by byly nalezeny všechny cesty, počet odkazů by se snížil na jedna a záznam by bylo možné z databáze smazat. Hezké je na tomto přístupu to, že velikost režie je omezena a zcela zmizí, když jsou nalezeny všechny cesty k relevantním inodům. Toto nicméně stále zavádí významné množství možná zbytečné komplexnosti; BSD implementace ukazuje, že mnoho aplikací šťastně běží s chováním pevných odkazů ne-zcela-podle-POSIXu.

V současnosti vrací rename() adresářů mezi větvemi EXDEV, chybu přesouvání souborů mezi různými souborovými systémy. Uživatelský prostor toto obvykle transparentně vyřeší (vzhledem k tomu, že tento případ musí řešit pro adresáře na různých souborových systémech) a použije kopírování obsahu adresáře jeden soubor po druhém. Implementace rekurzivního rename() adresářů mezi větvemi v jádře není nejlepší nápad ze stejných důvodů jako pro přejmenování mezi obyčejnými souborovými systémy; vracení EXDEV je pravděpodobně nejlepší řešení.

Z pohledu navrhování softwaru se sjednocující připojení jeví jako rozumný kompromis mezi vlastnostmi a jednoduchostí údržby. Většina změn ve VFS je izolována v fs/union.c, v souboru o cca 1000 řádkách. Přibližně 1/3 tohoto souboru je jaderná implementace readdir(), která bude téměř jistě před pokusem o začlenění nahrazena něčím jiným. Změny používaných souborových systémů jsou vcelku minimální a nutné pouze pro souborové systémy připojené jako zapisovatelné větve. Hlavní překážka začlenění tohoto kódu je implementace readdir(); správci souborových systémů byli jinak podstatně spokojenější se sjednocujícími připojeními než s jakoukoliv jinou implementací sjednocování.

Hezké shrnutí sjednocujících připojení lze nalézt ve slidech Bharaty B. Raa o sjednocujících připojení pro FOSS.IN [PDF].

Příště

V příštím článku projdeme unionfs a aufs a porovnáme různé implementace sjednocujících souborových systémů pro Linux. Zůstaňte na příjmu!

Diskuse k tomuto článku

[pepazdepa]

co si pamatuji tak treba na OpenBSD union uz neni, pry to nebylo stable... taky se union myslim zminoval v utocich na flagy UFS filesystemu a nekteri lidi tedy navrhovali vyhodit flagy uplne, pac to neni neprustrelne.

pekny clanek. diky

[Vskutečnosti Saýc]

Vybornej clanek.

[m;)]

autorka sa velmi rada cuduje, zda sa. priklady su len priklady (vid napr ten kde odporuca verzovacie nastroje). a davat ~/bin na zaciatok path nie je az taky dobry napad. mnohe systemy, ktore to s bezpecnostou myslia vazne, odporucaju presny opak.