Union filsystem: Implementations, part I


Denna artikel har tagits fram av LWN-prenumeranter

Prenumeranter på LWN.net har gjort denna artikel – och allt som omger den – möjlig. Om du uppskattar vårt innehåll, köp en prenumeration och gör nästa uppsättning artiklar möjliga.

25 mars 2009

Denna artikel har bidragits av Valerie Aurora (tidigare Henson)

I förra veckans artikel gick jag igenom användningsområden, grundläggande begrepp och vanliga konstruktionsproblem för unioning filsystem. Den här veckan kommer jag att beskriva flera implementeringar av unioning filsystem i teknisk detalj. De unioning-filsystem som jag kommer att ta upp i den här artikeln är Plan 9 uniondirectories, BSD union mounts, Linux union mounts. Nästa artikel kommer att täcka unionfs, aufs, och möjligen ett eller två andra unioning filsystem, och avsluta serien.

För varje filsystem kommer jag att beskriva dess grundläggande arkitektur, funktioner och implementering. Diskussionen om implementeringen kommer särskilt att fokusera på whiteouts och läsning av kataloger. Jag avslutar med en titt på de mjukvarutekniska aspekterna av varje implementering, t.ex. kodstorlek och komplexitet, invasivitet och börda för filsystemutvecklare.

Innan du läser den här artikeln kanske du vill läsa Andreas Grübachers nyss publicerade rapport om union mount-workshopen som hölls i november förra året. Det är en bra sammanfattning av de unioning-filsystemfunktioner som är mest angelägna för distributionsutvecklare. Från inledningen: ”Alla de användningsfall som vi är intresserade av går i princip ut på samma sak: att ha en avbildning eller ett filsystem som används skrivskyddat (antingen för att det inte är skrivbart eller för att det inte är önskvärt att skriva på avbildningen), och låtsas att denna avbildning eller detta filsystem är skrivbart, genom att lagra ändringar någon annanstans.”

Plan 9 union directories

Operativsystemet Plan 9 (bläddra i källkoden här) implementerar unioning på ett eget speciellt Plan 9-sätt. I Plan 9 unionskataloger slås endast den översta nivåns directorynamespace samman, inte eventuella underkataloger. Utan att begränsas av UNIX-standarderna tillämpar Plan 9 union directories inte whiteouts och sorterar inte ens bort dubbla poster – om samma filnamn förekommer i två filsystem återfinns det helt enkelt två gånger i directorylistorna.

En Plan 9 unionskatalog skapas så här:

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

Detta skulle leda till att katalogen/home/val/binunionmonteras ”efter” (alternativet-a)/bin; andraalternativ är att placera den nya katalogen före den befintliga katalogen, eller att ersätta den befintliga katalogen helt och hållet. (Detta verkar vara en märklig ordning för mig, eftersom jag vill att kommandon i min personliga

bin/ska ha företräde framför de systemomfattande kommandona, men det är exemplet från Plan 9-dokumentationen). Brian Kernighaneförklarar en av användningsområdena för unionskataloger: ”Denna mekanism med uniondirectories ersätter sökvägen i konventionella UNIX-skalor. När det gäller dig finns alla körbara program i /bin.” Uniondirectories kan teoretiskt sett ersätta många användningar av de grundläggande UNIX-byggstenarna symboliska länkar och sökvägar.

Utan whiteouts eller eliminering av dubbletter är readdir() onunion directories trivialt att implementera. Katalogpostens offset från det underliggande filsystemet motsvarar direkt katalogpostens offset i bytes från katalogens början. En unionskatalog behandlas som om innehållet i de underliggande katalogerna är sammanlänkade.

Plan 9 implementerar ett alternativ till readdir() som är värt att nämna, dirread().dirread() returnerar strukturer av typen Dir, som beskrivs i man-sidan stat()man. Den viktiga delen av Dir är medlemmen Qid. En Qid är:

…en struktur som innehåller fälten path och vers: path är garanterad att vara unik bland alla path-namn som för närvarande finns på filservern, och vers ändras varje gång filen ändras. Path är en long long (64 bitar, vlong) och vers är en unsigned long (32 bitar, ulong).

Varför är detta intressant? En av anledningarna till att readdir() är så jobbig att implementera är att den returnerar d_off-medlemmen i struct dirent, som en enda off_t (32 bitar om inte programmet är kompilerat med stöd för stora filer), för att markera den katalogpost där ett program ska fortsätta läsa vid nästa readdir()-anrop. Detta fungerar bra så länge d_off är en enkel byteoffset i en platt fil på mindre än 232 byte och befintliga katalogposter aldrig flyttas runt – vilket inte är fallet för många moderna filsystem (XFS, btrfs, ext3 med htree-index). Den 96-bitars Qid är en mycket mer användbar platsmarkör än den 32- eller 64-bitars off_t. För en bra sammanfattning av problemen med att implementera readdir(), läs TheodoreY. Ts’o’s utmärkta inlägg om ämnet på btrfs mailing list.

Från en mjukvaruteknisk synvinkel är Plan 9 union directories himmelskt bra. Utan whiteouts, eliminering av dubbla poster, komplicerade katalogförskjutningar eller sammanslagning av namnområden bortom den översta nivåns katalog är genomförandet enkelt och lätt att underhålla.Varje praktiskt genomförande av unioning-filsystem för Linux (eller något annat UNIX) skulle dock behöva lösa dessa problem. För våra syften tjänar Plan 9:s unionkataloger främst som inspiration.

BSD union mounts

BSD implementerar två former av unioning:"-o union"alternativet tillmount-kommandot, som ger en unionkatalog som liknar Plan 9:s, ochmount_unionfs-kommandot, som implementerar ett mer fullfjädrade unioning-filsystem med whiteouts och sammanslagning av hela namnrymden. Vi kommer att fokusera på den sistnämnda.

För den här artikeln använder vi två källor för specifika implementeringsdetaljer: den ursprungliga BSD union mount-implementeringen som beskrivs i USENIX-artikelnUnionmounts in 4.4BSD-Lite från 1995, och FreeBSD7.1 mount_unionfss man-sida och källkod. Andra BBSD:er kan variera.

En katalog kan unionmonteras antingen ”under” eller ”över” en befintlig katalog eller unionmontering, så länge som den översta grenen av en skrivbar union är skrivbar. Det finns stöd för två typer av whiteouts: antingen skapas en whiteout alltid när en katalog tas bort, eller så skapas den bara om en annan katalogpost med det namnet för närvarande finns i en gren under den skrivbara grenen. Tre lägen för att ställa in ägarskap och läge för kopierade filer stöds. Det enklaste ärtransparent, där den nya filen behåller samma ägare och läge som originalet. Läget masquerade gör att de kopierade filerna ägs av en viss användare och stödjer en uppsättning mount-alternativ för att bestämma den nya filens läge.Läget traditional ställer in ägaren till den användare som ranthe union mount-kommandot, och ställer in läget i enlighet med umask vid tidpunkten för union mount.

Varje gång en katalog öppnas skapas en katalog med samma namn på det översta skrivbara skiktet om den inte redan finns. Ur dokumentet:

Då unionfilesystemet genom att skapa skuggkataloger aggressivt under uppslaget undviker att behöva kontrollera och eventuellt skapa kedjan av kataloger från roten av mountet till punkten för en copy-up.Eftersom det diskutrymme som förbrukas av en katalog är försumbart, verkade det vara ett bättre alternativ att skapa kataloger när de först genomkorsas.

Som ett resultat kommer en "find /union" att resultera i att alla kataloger (men inte katalogposter som pekar på icke-kataloger) kopieras till det skrivbara lagret. För de flesta filsystemavbildningar kommer detta att använda en obetydlig mängd utrymme (mindre än t.ex. det utrymme som är reserverat för rotanvändaren, eller det som tas upp av oanvända inoder i ett FFS-liknande filsystem).

En fil kopieras upp till det översta lagret när den öppnas med skrivbehörighet eller när filattributen ändras. (Eftersom kataloger kopieras över när de öppnas är det garanterat att den katalog som innehåller den redan finns på det skrivbara lagret). Om filen som ska kopieras upp har flera hårda länkar ignoreras de andra länkarna och den nya filen har ett länkantal på en. Detta kan bryta program som använder hårda länkar och förväntar sig att ändringar via ett länknamn ska visas när de refereras via en annan hård länk. Sådana tillämpningar är relativt ovanliga, men ingen har gjort en systematisk studie för att se vilka tillämpningar som kommer att misslyckas i denna situation.

Whiteouts implementeras med en speciell katalogposttyp, DH_WHT. Whiteout-katalogposter hänvisar inte till någon riktig inode, men för att underlätta kompatibiliteten med befintliga filsystemfunktioner som fsck innehåller varje whiteout-katalogpost ett falskt inodnummer, det WINO reserverade whiteout-inodnumret. Det underliggande filsystemet måste ändras för att stödja typen whiteout directory entry. Nya kataloger som ersätter en whiteout-post markeras som opaka via ett nytt ”opaque” inodeattribut så att sökningar inte går igenom dem (vilket återigen kräver minimalt stöd från det underliggande filsystemet).

Duplicerade katalogposter och whiteouts hanteras i implementationen i användarutrymmetreaddir(). Vid opendir()tillfället läser C-biblioteket katalogen på en gång, tar bort dubbletter, tillämpar whiteouts och cachas resultatet.

BSD union mounts försöker inte hantera ändringar av grenar under den skrivbara översta grenen (även om de är tillåtna). Hur rename() hanteras är inte beskrivet.

Ett exempel från man-sidan mount_unionfs:

 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.

Ett annat exempel (med en anmärkning om att jag anser att källkontroll är bäst genomförd utanför filsystemet):

 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

Likt BSD union mounts implementerar Linux union mounts filsystemunionering i VFS-skiktet, med lite mindre stöd från underliggande filsystem för whiteouts och opaka katalogtaggar. Det finns flera versioner av dessa patchar, skrivna och modifierade av bland annat Jan Blunck, Bharata B. Rao och Miklos Szeredi.

En version av den här koden sammanfogar endast katalogerna på den översta nivån, i likhet med Plan 9 union directories och BSD -o unionmount-alternativet. Denna version av union mounts, som jag kallar uniondirectories, beskrivs ganska detaljerat i en nyligen publicerad LWN-artikel av Goldwyn Rodrigues och i Miklos Szeredis nyligen publicerade inlägg med en uppdaterad patchuppsättning. I resten av den här artikeln kommer vi att fokusera på versioner av union mount som sammanfogar den fullständiga namnrymden.

Linux union mounts är för närvarande under aktiv utveckling. Den här artikeln beskriver den version som Jan Blunck släppte mot Linux2.6.25-mm1, util-linux 2.13 och e2fsprogs 1.40.2. Patchuppsättningarna kan laddas ner från Jans ftp-webbplats:

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

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

Jag har skapat en webbsida med länkar till git-versioner av ovanstående patchar och en del dokumentation i HOWTO-stil på http://valerieaurora.org/union.

En union skapas genom att montera ett filsystem med flagguppsättningen MS_UNION. (MS_BEFORE, MS_AFTERoch MS_REPLACE är definierade i mount-kodbasen men används inte för närvarande.) Om flaggan MS_UNION specificeras måste det monterade filsystemet antingen vara skrivskyddat eller stödja whiteouts. I den här versionen av union mounts specificeras union mountflaggen av alternativet ”-o union” till mount. För att till exempel skapa en union av två loopbackdevice-filsystem, /img/ro och /img/rw, skulle du köra:

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

Varje union mount skapar enstruct 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 */ };

Som beskrivet iDocumentation/filesystems/union-mounts.txt: ”Allaunion_mount-strukturer cachelagras i två hashtabeller, en för sökningar i nästa lägre lager i unionstacken och en för omvända sökningar i nästa högre lager i unionstacken.”

Varjeflaggor och ogenomskinliga kataloger implementeras på ungefär samma sätt som i BSD. Det underliggande filsystemet måste uttryckligen stödja whiteouts genom att definiera inodeoperationen .whiteout för kataloger (för närvarande är whiteouts endast implementerade för ext2, ext3 och tmpfs). ext2- och ext3-implementationerna använder whiteout directory entrytype, DT_WHT, som har definierats i include/linux/fs.h i flera år, men som inte har använts utanför Coda-filsystemet förrän nu. Ett reserverat whiteout inodenummer, EXT3_WHT_INO, är definierat men används ännu inte; whiteoutposter allokerar för närvarande en normal inod. Ett nytt inodeflag, S_OPAQUE, har definierats för att markera kataloger som opaka.Liksom i BSD markeras kataloger endast som opaka när de ersätter en whiteout-post.

Filer kopieras upp när filen öppnas för skrivning. Om det är nödvändigt kopieras varje katalog i sökvägen till filen till den övre filialen (copy-on-demand av kataloger). För närvarande stöds kopiering uppåt endast för vanliga filer och kataloger.

readdir() är en av de svagaste punkterna i den nuvarande implementeringen. Den implementeras på samma sätt som BSD union mountreaddir(), men i kärnan. d_offfältet sätts till förskjutningen inom den aktuella underliggande katalogen,minus storleken på de tidigare katalogerna. Katalogposter från kataloger under det översta lagret måste kontrolleras mot tidigare poster för att upptäcka dubbletter eller whiteouts. Som det för närvarande är implementerat läser varje readdir() (tekniskt sett getdents()) systemanrop alla tidigare katalogposter i en cache i kärnan och jämför sedan varje post som skall returneras med dem som redan finns i cacheminnet innan den kopieras till användarbufferten. Slutresultatet är att readdir() är komplicerat, långsamt och kan potentiellt allokera en stor mängd kärnminne.

En lösning är att följa BSD:s tillvägagångssätt och göra caching, whiteout och duplikatbehandling i användarutrymmet. Bharata B. Raois designar stöd för union mount readdir() i glibc (POSIX-standarden tillåter att readdir() implementeras på libc-nivå om kärnans rena systemanrop inte uppfyller alla krav). Detta skulle flytta minnesanvändningen till programmet och göra cacheminnet beständigt. En annan lösning skulle vara att göra cacheminnet i kärnan beständigt på något sätt.

Mitt förslag är att ta en teknik från BSD union mounts och utvidga den: kopiera proaktivt upp inte bara katalogposter för kataloger, utan alla katalogposter från lägre filsystem, bearbeta dubbletter och whiteouts, göra katalogen ogenomskinlig och skriva ut den på disk. I själva verket bearbetar du katalogposterna för whiteouts och dubbletter vid första öppnandet av katalogen och skriver sedan den resulterande ”cachen” av katalogposter till disken. De katalogposter som pekar på filer i de underliggande filsystemen måste på något sätt ange att de är ”fall-through”-poster (motsatsen till en whiteout – den begär uttryckligen att man skall söka upp ett objekt i ett lägre filsystem). En sidoeffekt av detta tillvägagångssätt är att whiteouts inte längre behövs alls.

Ett problem som måste lösas med detta tillvägagångssätt är hur katalogposter som pekar på lägre filsystem skall representeras. Ett antal lösningar är möjliga: posten kan peka på ett reserverat inodnummer, filsystemet kan allokera en inod för varje post men markera den med ett nytt S_LOOKOVERTHERE inodeattribut, det kan skapa en symbolisk länk till ett reserverat mål, osv. Detta tillvägagångssätt skulle använda mer utrymme på det överliggande filsystemet, men alla andra tillvägagångssätt kräver att samma utrymme allokeras i minnet, och i allmänhet är minnet dyrare än disken.

Ett mindre angeläget problem med den nuvarande implementeringen är att inodenumren inte är stabila över hela uppstarten (se den tidigare artikeln om unioning file systems för mer information om varför detta är ett problem).Om ”fall-through”-kataloger implementeras genom att allokera en inode för varje katalogpost på de underliggande filsystemen, så kommer stabila inodenummer att vara en naturlig bieffekt. Ett annat alternativ är att lagra en beständig inodemappning någonstans – i en fil i den översta katalogen eller kanske i ett externt filsystem.

Hårdlänkar hanteras – eller rättare sagt, hanteras inte – på samma sätt som BSD union mounts. Återigen är det inte klart hur många tillämpningar som är beroende av att ändra en fil via en hårdlänkad sökväg och se ändringarna via en annan hårdlänkad sökväg (i motsats till symbolisk länk). Den enda metod som jag kan komma på för att hantera detta på ett korrekt sätt är att hålla en permanent cache någonstans på disken av de inoder som vi har stött på med flera hårda länkar.

Här är ett exempel på hur det skulle fungera: Säg att vi startar en kopia för inod 42 och upptäcker att den har ett länkantal på tre. Vi skulle skapa en post för hard link-databasen som innehåller filsystemets id,inode-numret, länkantalet och inode-numret för den nya kopian på det översta filsystemet. Det kan lagras i en fil i CSV-format eller som en symbolisk länk i en reserverad katalog i rotkatalogen (t.ex. ”/.hardlink_hack/<fs_id>/42”, som är en länk till ”<new_inode_num> 3”) eller i en riktig databas. Varje gång vi öppnar en inod i ett underliggande filsystem söker vi upp den i vår databas för hårda länkar. Om det finns en post minskar vi antalet länkar och skapar en hård länk till rätt inod i det nya filsystemet. När alla sökvägar har hittats sjunker antalet länkar till ett och posten kan tas bort från databasen. Det fina med detta tillvägagångssätt är att mängden overhead är begränsad och kommer att försvinna helt och hållet när alla vägar till de relevanta inoderna har letats upp. BSD-implementationen visar att många program gärna körs med ett inte helt POSIXLY-korrekt hardlinkbeteende.

För närvarande ger rename() av kataloger i olika filialer EXDEV, felet när man försöker byta namn på en fil i olika filsystem. Användarutrymmet hanterar vanligtvis detta på ett genomskinligt sätt (eftersom det redan måste hantera detta fall för kataloger från olika filsystem) och återgår till att kopiera innehållet i katalogen en efter en. Att implementera rekursivt rename() av kataloger över grenar i kärnan är inte en lysande idé av samma skäl som att byta namn över regelbundna filsystem; troligen är det bästa sättet att returnera EXDEV.

Från en mjukvaruteknisk synvinkel verkar union mounts vara en rimlig kompromiss mellan funktionalitet och enkelhet i underhållet. De flesta av VFS-ändringarna är isolerade i fs/union.c, en fil med ungefär 1000 rader. Ungefär 1/3 av denna fil utgörs av implementationen av readdir() i kärnan, som nästan säkert kommer att ersättas av något annat före en eventuell sammanslagning. ändringarna av de underliggande filsystemen är ganska minimala och behövs endast för filsystem som monteras som skrivbara grenar. Det största hindret för en sammanslagning av denna kod är readdir()implementationen. I övrigt har filsystemsansvariga varit märkbart mer positiva till union mounts än någon annan unioningimplementation.

En bra sammanfattning av union mounts finns i Bharata B. Raos union mount-slides för FOSS.IN .

Nästa artikel

I nästa artikel kommer vi att gå igenom unionfs och aufs, och jämföra de olika implementeringarna av unioning-filsystem för Linux. Håll dig uppdaterad!

Indexposter för denna artikel
Kernel Filsystem/Union
Kernel Union mounts
Gästartiklar Aurora (Henson), Valerie

Lämna ett svar

Din e-postadress kommer inte publiceras.