Union file systems: Implementations, part I


Dit artikel is mogelijk gemaakt door LWN abonnees

Abonnees van LWN.net hebben dit artikel – en alles wat er omheen staat – mogelijk gemaakt. Als u onze inhoud waardeert, neem dan een abonnement en maak de volgende artikelen mogelijk.

Maart 25, 2009

Dit artikel is geschreven door Valerie Aurora (voorheen Henson)

In het artikel van vorige week heb ik de gebruikssituaties, basisconcepten en algemene ontwerpproblemen van unioning bestandssystemen besproken. Deze week beschrijf ik verschillende implementaties van unioning bestandssystemen in technisch detail. De unioning bestandssystemen die ik in dit artikel zal behandelen zijn Plan 9 union mappen, BSD union mounts, Linux union mounts. Het volgende artikel zal unionfs, aufs, en mogelijk een of twee andere unioning bestandssystemen behandelen, en de serie afronden.

Voor ieder bestandssysteem zal ik de basis architectuur, mogelijkheden, en implementatie beschrijven. De discussie over de implementatie zal zich in het bijzonder richten op whiteouts en het lezen van mappen. Ik sluit af met een blik op de software engineering aspecten van elke implementatie; b.v. code grootte en complexiteit, invasiviteit, en belasting voor file systeem ontwikkelaars.

Voordat je dit artikel leest, wil je misschien AndreasGruenbacher’s zojuist gepubliceerde verslag van de union mount workshop van afgelopen november bekijken. Het is een goede samenvatting van de unioning bestandssysteem-kenmerken die het meest urgent zijn voor distributie-ontwikkelaars. Uit de inleiding: “Alle gebruikssituaties waarin we geïnteresseerd zijn komen in principe op hetzelfde neer: een image of bestandssysteem hebben dat alleen-lezen wordt gebruikt (omdat het niet beschrijfbaar is, of omdat schrijven naar het image niet gewenst is), en doen alsof dit image of bestandssysteem beschrijfbaar is, waarbij wijzigingen ergens anders worden opgeslagen.”

Plan 9 union directories

Het Plan 9 besturingssysteem (browseables broncode hier) implementeert unioning op zijn eigen speciale Plan 9 manier. In Plan 9 union directories wordt alleen de top-level directorynaamruimte samengevoegd, geen subdirectories. Niet beperkt door UNIX-standaarden, implementeren Plan 9 union directories geen white-outs en weren zelfs geen dubbele entries – als dezelfde bestandsnaam in twee bestandssystemen voorkomt, wordt deze gewoon twee keer geretourneerd in directory-lijsten.

Een Plan 9 union directory wordt als volgt aangemaakt:

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

Dit zorgt ervoor dat de directory

/home/val/binwordt gemount “na” (de-aoptie)/bin; andere opties zijn om de nieuwe directory vóór de bestaande directory te plaatsen, of om de bestaande directory geheel te vervangen. (Dit lijkt mij een vreemde volgorde, omdat ik graag heb dat commando’s in mijn persoonlijkebin/voorrang krijgen boven de systeemwijde commando’s, maar dat is het voorbeeld uit de Plan 9 documentatie). Brian Kernighane legt een van de toepassingen van union directories uit: “Dit mechanisme van uniondirectories vervangt het zoekpad van conventionele UNIX-shells. Voor zover het jou betreft, bevinden alle uitvoerbare programma’s zich in /bin.” Uniondirectories kunnen theoretisch vele toepassingen van de fundamenteleUNIX-bouwstenen symbolische links en zoekpaden vervangen.

Zonder whiteouts of duplicaat-eliminatie is readdir()oniondirectories triviaal te implementeren. De offsets van de directory-items van het onderliggende bestandssysteem komen direct overeen met de offset in bytes van de directory-item vanaf het begin van de directory. Eenunion directory wordt behandeld alsof de inhoud van de onderliggende directories aan elkaar zijn geplakt.

Plan 9 implementeert een alternatief voor readdir() dat het vermelden waard is, dirread().dirread() retourneert structuren van het type Dir, beschreven in de stat()man page. Het belangrijke deel van de Dir is het Qid lid. Een Qid is:

…een structuur met pad- en vers-velden: het pad is gegarandeerd uniek onder alle padnamen die momenteel op de bestandsserver staan, en vers verandert elke keer dat het bestand wordt gewijzigd. Het pad is een lange long (64 bits, vlong) en de vers is een unsigned long (32 bits, ulong).

Dus waarom is dit interessant? Een van de redenen waarom readdir() zo lastig te implementeren is, is dat het d_off lid van struct dirent terugstuurt, een enkele off_t (32 bits, tenzij de applicatie is gecompileerd met ondersteuning voor grote bestanden), om de directory entry te markeren waar een applicatie moet doorgaan met lezen bij de volgende readdir() aanroep. Dit werkt prima zolang d_off een eenvoudige byte-offset is in een plat bestand van minder dan 232 bytes en bestaande directory-entries nooit worden verplaatst – niet het geval voor veel moderne bestandssystemen (XFS, btrfs, ext3 met htree indexes). De 96-bit Qid is een veel bruikbaardere plaatsaanduiding dan de 32- of 64-bit off_t. Voor een goede samenvatting van de problemen die komen kijken bij het implementeren van readdir(), lees TheodoreY. Ts’o’s uitstekende post over het onderwerp op de btrfs mailing list.

Vanuit een software-engineering standpunt, Plan 9 union directories zijn hemels. Zonder whiteouts, dubbele entry eliminatie, gecompliceerde directory offsets, of het samenvoegen van namespaces voorbij de top-leveldirectory, is de implementatie eenvoudig en gemakkelijk te onderhouden.Echter, elke praktische implementatie van unioning bestandssystemen voor Linux (of enige andere UNIX) zou deze problemen moeten oplossen. Voor ons doel dienen Plan 9 union directories voornamelijk als inspiratie.

BSD union mounts

BSD implementeert twee vormen van unioning: de"-o union"optie voor hetmountcommando, die een union directory produceert die lijkt op die van Plan 9, en hetmount_unionfscommando, dat een meer volledig functioneel unioning bestandssysteem implementeert met whiteouts en samenvoeging van de gehele namespace. Voor dit artikel gebruiken we twee bronnen voor specifieke implementatiedetails: de originele BSD union mount-implementatie zoals beschreven in het USENIX documentUnionmounts in 4.4BSD-Lite uit 1995, en de FreeBSD7.1mount_unionfsman page en broncode. AndereBSD’s kunnen afwijken.

Een map kan zowel “onder” als “boven” een bestaande map of union mount worden gemount, zolang de bovenste tak van een schrijfbare union schrijfbaar is. Twee manieren van whiteouts worden ondersteund: ofwel wordt een whiteout altijd aangemaakt wanneer een map wordt verwijderd, ofwel wordt hij alleen aangemaakt als een andere mapentry met die naam op dat moment bestaat in een tak onder de beschrijfbare tak. Drie modi voor het instellen van het eigenaarschap en de modus van gekopieerde bestanden worden ondersteund. De eenvoudigste istransparent, waarbij het nieuwe bestand dezelfde eigenaar en modus behoudt als het originele. De masquerade modus maakt de gekopieerde bestanden eigendom van een bepaalde gebruiker en ondersteunt een set mount opties om de nieuwe bestandsmodus te bepalen. De traditional modus stelt de eigenaar in op de gebruiker die het union mount commando uitvoert, en stelt de modus in volgens de umask op het moment van de union mount.

Wanneer een directory wordt geopend, wordt een directory met dezelfde naam aangemaakt op de bovenste beschrijfbare laag als die nog niet bestaat. Uit de paper:

Door het agressief aanmaken van schaduwmappen tijdens het opzoeken vermijdt het unionfilesysteem dat de keten van mappen van de root van de mount tot het punt van een kopie-up moet worden nagekeken en eventueel aangemaakt.Omdat de schijfruimte die een directory inneemt verwaarloosbaar is, leek het een beter alternatief om directories aan te maken op het moment dat ze voor het eerst werden bezocht.

Als gevolg hiervan zal een "find /union" resulteren in het kopiëren van elke directory (maar niet directory entries die naar niet-directories wijzen) naar de beschrijfbare laag. Voor de meeste bestandssysteem-images zal dit een verwaarloosbare hoeveelheid ruimte gebruiken (minder dan, bijvoorbeeld, de ruimte die is gereserveerd voor de root-gebruiker, of de ruimte die wordt ingenomen door ongebruikte inodes in een FFS-stijl bestandssysteem).

Een bestand wordt naar de bovenste laag gekopieerd wanneer het wordt geopend met schrijfrechten of wanneer de bestandskenmerken worden gewijzigd. (Aangezien mappen worden gekopieerd wanneer ze worden geopend, is de bevattende map gegarandeerd al aanwezig op de beschrijfbare laag). Als het te kopiëren bestand meerdere hard links heeft, worden de andere links genegeerd en heeft het nieuwe bestand een linktelling van één. Dit kan toepassingen onderbreken die hard links gebruiken en verwachten dat wijzigingen via één linknaam zichtbaar worden als er via een andere hard link naar verwezen wordt. Zulke toepassingen zijn relatief ongewoon, maar niemand heeft een systematische studie gedaan om te zien welke toepassingen in deze situatie zullen falen.

Whiteouts worden geïmplementeerd met een speciaal directory entry-type, DH_WHT. Whiteout directory-entries verwijzen niet naar een echte inode, maar voor gemakkelijke compatibiliteit met bestaande bestandssysteemutilities zoals fsck, bevat elke whiteout directory-entry een vals inode-nummer, het WINO gereserveerde whiteoutinode-nummer. Het onderliggende bestandssysteem moet worden aangepast om het whiteout map item type te ondersteunen. Nieuwe mappen die een whiteout-entry vervangen, worden als ondoorzichtig gemarkeerd via een nieuw “ondoorzichtig” inode-attribuut, zodat lookups er niet doorheen reizen (waarvoor opnieuw minimale ondersteuning van het onderliggende bestandssysteem nodig is).

Duplicate directory-entries en whiteouts worden afgehandeld in de gebruikersruimtereaddir() implementatie. Op opendir()tijd leest de C bibliotheek de directory in een keer, verwijdert de dubbele vermeldingen, past whiteouts toe, en slaat de resultaten op in een cache.

BSD union mounts proberen niet om te gaan met wijzigingen aan takken onder de beschrijfbare top branch (hoewel ze zijn toegestaan). De manier waarop rename() wordt afgehandeld is niet beschreven.

Een voorbeeld uit de mount_unionfs man page:

 The commands mount -t cd9660 -o ro /dev/cd0 /usr/src mount -t unionfs -o noatime /var/obj /usr/src mount the CD-ROM drive /dev/cd0 on /usr/src and then attaches /var/obj on top. For most purposes the effect of this is to make the source tree appear writable even though it is stored on a CD-ROM. The -o noatime option is useful to avoid unnecessary copying from the lower to the upper layer.

Another example (noting that I believe source control is bestimplemented outside of the file system):

 The command mount -t unionfs -o noatime -o below /sys $HOME/sys attaches the system source tree below the sys directory in the user's home directory. This allows individual users to make private changes to the source, and build new kernels, without those changes becoming visible to other users.

Linux union mounts

Zoals BSD union mounts, implementeert Linux union mounts bestandssysteem unioning in de VFS laag, met wat kleine ondersteuning van onderliggende bestandssystemen voor whiteouts en ondoorzichtige directory tags. Er bestaan verschillende versies van deze patches, geschreven en aangepast door Jan Blunck, Bharata B. Rao, en Miklos Szeredi, onder anderen.

Een versie van deze code voegt alleen de top-level directories samen, vergelijkbaar met Plan 9 union directories en de BSD -o unionmount optie. Deze versie van union mounts, waarnaar ik verwijs als uniondirectories, worden in enig detail beschreven in een recent LWN artikel doorGoldwyn Rodrigues en in Miklos Szeredi’s recente post van een bijgewerkte patch set. Voor de rest van dit artikel, zullen we ons richten op versies van union mounts die de volledige naamruimte samenvoegen.

Linux union mounts zijn momenteel in actieve ontwikkeling. Dit artikel beschrijft de versie die is uitgebracht door Jan Blunck tegen Linux2.6.25-mm1, util-linux 2.13, en e2fsprogs 1.40.2. De patch sets, alsquilt series, kunnen worden gedownload van Jan’s ftp site:

Kernel patches: ftp://ftp.suse.com/pub/people/jblunck/patches/

Utilities: ftp://ftp.suse.com/pub/people/jblunck/union-mount/

Ik heb een webpagina gemaakt met links naar git-versies van de bovenstaande patches en wat HOWTO-achtige documentatie op http://valerieaurora.org/union.

Een union wordt gemaakt door een bestandssysteem te mounten met de MS_UNION flagset. (De MS_BEFORE, MS_AFTER,en MS_REPLACE zijn gedefinieerd in de mount codebase maar worden momenteel niet gebruikt.) Als de vlag MS_UNION is gespecificeerd, dan moet het aangekoppelde bestandssysteem ofwel alleen-lezen zijn ofwel whiteouts ondersteunen. In deze versie van union mounts, wordt de union mountflag gespecificeerd door de “-o union” optie bij mount. Om bijvoorbeeld een unie te maken van twee loopbackdevice bestandssystemen, /img/ro en /img/rw, zou je uitvoeren:

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

Elke union mount maakt eenstruct 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 */ };

Zoals beschreven inDocumentation/filesystems/union-mounts.txt, “Allunion_mount structures are cached in two hash tables, one for lookupsof the next lower layer of the union stack and one for reverse lookupsof the next upper layer of the union stack.”

Whiteouts en ondoorzichtige mappen worden op vrijwel dezelfde manier geïmplementeerd als in BSD. Het onderliggende bestandssysteem moet expliciet whiteouts ondersteunen door de .whiteout inode operatie voor directories te definiëren (momenteel zijn whiteouts alleen geïmplementeerd voor ext2, ext3, en tmpfs). De implementaties van ext2 en ext3 gebruiken het whiteout directory entrytype, DT_WHT, dat al jaren gedefinieerd is in include/linux/fs.h maar tot nu toe niet gebruikt werd buiten het Coda bestandssysteem. Een gereserveerd whiteout inodenummer, EXT3_WHT_INO, is gedefinieerd maar wordt nog niet gebruikt; whiteout entries wijzen momenteel een normale inode toe. Een nieuwe inodeflag, S_OPAQUE, is gedefinieerd om directories als ondoorzichtig te markeren.Net als in BSD, worden directories alleen als ondoorzichtig gemarkeerd wanneer ze een whiteout entry vervangen.

Bestanden worden omhoog gekopieerd wanneer het bestand wordt geopend voor schrijven. Indien nodig wordt elke directory in het pad naar het bestand naar de bovenste tak gekopieerd (copy-on-demand van directories). Momenteel wordt kopiëren alleen ondersteund voor gewone bestanden en mappen.

readdir() is een van de zwakste punten van de huidige implementatie. Het is op dezelfde manier geïmplementeerd als BSD union mountreaddir(), maar dan in de kernel. Het d_off-veld wordt ingesteld op de offset binnen de huidige onderliggende directory, minus de afmetingen van de voorgaande directories. De directory entries van de directories onder de bovenste laag moeten worden gecontroleerd tegen de vorige entries voor duplicaten of whiteouts. Zoals momenteel geïmplementeerd, leest elke readdir() (technisch gezien getdents())-systeemaanroep alle voorgaande directory-entries in een cache in de kernel, vergelijkt dan elke entry die wordt geretourneerd met de entries die al in de cache staan voordat deze naar de gebruikersbuffer wordt gekopieerd. Het eindresultaat is dat readdir() complex en traag is, en mogelijk veel kernelgeheugen toewijst.

Een oplossing is om de BSD-benadering te volgen en de caching, whiteout, en dubbele verwerking in gebruikersruimte te doen. Bharata B. Raois ontwerpt ondersteuning voor union mount readdir() in glibc. (De POSIX standaard staat toe dat readdir() wordt geïmplementeerd op libc niveau als de kale kernel system call niet aan alle eisen voldoet). Dit zou het geheugengebruik naar de applicatie verplaatsen en de cache persistent maken. Een andere oplossing zou zijn om de in-kernel cache op de een of andere manier persistent te maken.

Mijn suggestie is om een techniek van BSD union mounts te nemen en die uit te breiden: kopieer pro-actief niet alleen directory entries voor directories, maar alle directory entries van lagere bestandssystemen, verwerk duplicaten en white-outs, maak de directory ondoorzichtig, en schrijf hem weg naar schijf. In feite worden de vermeldingen in de map bij de eerste keer dat de map wordt geopend, verwerkt op whiteouts en duplicaten, en wordt de resulterende “cache” van mapvermeldingen naar de schijf geschreven. De directory-entries die naar bestanden op de onderliggende bestandssystemen wijzen, moeten op de een of andere manier aangeven dat het “fall-through” entries zijn (het tegenovergestelde van een whiteout – het vraagt expliciet om een object in een lager bestandssysteem op te zoeken). Een neveneffect van deze aanpak is dat whiteouts helemaal niet meer nodig zijn.

Een probleem dat met deze aanpak moet worden opgelost, is hoe directory-entries die naar lagere bestandssystemen verwijzen, moeten worden voorgesteld. Een aantal oplossingen dient zich aan: de ingang zou kunnen verwijzen naar een gereserveerd nodelijnnummer, het bestandssysteem zou een inode kunnen toewijzen voor elke ingang maar deze markeren met een nieuw S_LOOKOVERTHERE inode-attribuut, het zou een symlink kunnen maken naar een gereserveerd doel, enz. Deze benadering zou meer ruimte gebruiken op het bovenliggende bestandssysteem, maar alle andere benaderingen vereisen het toewijzen van dezelfde ruimte in geheugen, en over het algemeen is geheugen kostbaarder dan schijf.

Een minder urgent probleem met de huidige implementatie is dat inodenummers niet stabiel zijn bij het opstarten (zie het vorige unioning bestandssystemen artikel voor details over waarom dit een probleem is).Als “fall-through” directories worden geïmplementeerd door een inode toe te wijzen voor elke directory entry op onderliggende bestandssystemen, dan zullen stabiele inodenummers een natuurlijk neveneffect zijn. Een andere optie is om ergens een consistente inode map op te slaan – in een bestand in de top-level directory, of in een extern bestandssysteem, misschien.

Hard links worden behandeld – of, nauwkeuriger gezegd, niet behandeld – op dezelfde manier als BSD union mounts. Ook hier is het niet duidelijk hoeveel toepassingen afhankelijk zijn van het wijzigen van een bestand via een hard-linked pad en het zien van de wijzigingen via een ander hard-linked pad (in tegenstelling tot een symbolic-link). De enige methode die ik kan bedenken om dit goed te regelen is om ergens op schijf een persistente cache bij te houden van de inodes die we hebben tegengekomen met meerdere hard-links.

Hier volgt een voorbeeld van hoe het zou werken: Stel dat we een kopie maken van inode 42 en ontdekken dat deze een linktelling van drie heeft. We zouden een item maken voor de hard link database dat het bestandssysteem id, het knooppuntnummer, het aantal koppelingen, en het inode nummer van de nieuwe kopie op het top level bestandssysteem bevat. Dit kan worden opgeslagen in een bestand in CSV-formaat, of als een symlink in een gereserveerde directory in de hoofddirectory (b.v. “/.hardlink_hack/<fs_id>/42“, die een link is naar “<new_inode_num> 3“), of in een echte database. Telkens als we een inode openen op een onderliggend bestandssysteem, zoeken we die op in onze hard link database; als er een entry bestaat, verminderen we het aantal links en maken een hard link naar de juiste inode op het nieuwe bestandssysteem. Wanneer alle paden gevonden zijn, daalt de linktelling tot één en kan de entry uit de database verwijderd worden. Het mooie van deze aanpak is dat de hoeveelheid overhead begrensd is en volledig zal verdwijnen wanneer alle paden naar de relevante inodes zijn opgezocht. Dit introduceert echter nog steeds een aanzienlijke hoeveelheid mogelijk onnodige complexiteit; de BSD-implementatie laat zien dat veel applicaties gelukkig zullen draaien met niet helemaal POSIXLY-correct hardlink gedrag.

Tegenwoordig geeft rename() van directories over filialen heen EXDEV, de fout bij het proberen te hernoemen van een bestand over verschillende bestandssystemen heen. De gebruikersruimte handelt dit gewoonlijk ondoorzichtig af (omdat het dit geval al moet afhandelen voor mappen van verschillende bestandssystemen) en valt terug op het één voor één kopiëren van de inhoud van de map. Het implementeren van recursieve rename() van mappen over vertakkingen in de kernel is geen slim idee om dezelfde redenen als hernoemen over reguliere bestandssystemen; waarschijnlijk is het teruggeven van EXDEV de beste oplossing.

Vanuit het oogpunt van software-engineering, lijken union mounts een redelijk compromis tussen mogelijkheden en onderhoudsgemak. De meeste VFS-wijzigingen zijn geïsoleerd in fs/union.c, een bestand van ongeveer 1000 regels. Ongeveer 1/3 van dit bestand is de readdir() implementatie in de kernel, die vrijwel zeker vervangen zal worden door iets anders voordat een mogelijke samenvoeging plaatsvindt. De veranderingen aan de onderliggende bestandssystemen zijn vrij minimaal en alleen nodig voor bestandssystemen die als beschrijfbare takken gemount zijn. Het grootste obstakel voor het samenvoegen van deze code is de readdir()-implementatie. Voor de rest zijn beheerders van bestandssystemen merkbaar positiever over union mounts dan over elke andere unioning-implementatie.

Een mooie samenvatting van union mounts is te vinden in Bharata B. Rao’s union mount slides voor FOSS.IN.

Komt nog

In het volgende artikel zullen we unionfs en aufs bespreken, en de verschillende implementaties van unioning bestandssystemen voor Linux vergelijken. Blijf op de hoogte!

Indexitems voor dit artikel
Kernel Filesystemss/Union
Kernel Union mounts
Gastartikels Aurora (Henson), Valerie

Geef een antwoord

Het e-mailadres wordt niet gepubliceerd.