11. cvičenie – súborový systém ?️

Súborový systém

Na tomto cvičení pridáte do súborového systému xv6 podporu veľkých súborov a symbolických odkazov.

Predtým, než sa pustíte do písania kódu, prečítajte si kapitolu 7 File system z xv6 knižky a preštudujte si príslušný kód.

Vo svojom repozitári sa prepnite do vetvy util:

Veľké súbory

V prvej časti cvičenia zvýšite maximálnu podporovanú veľkosť súboru v xv6. Veľkosť súborov v xv6 je aktuálne obmedzená na 268 blokov, teda 268*BSIZE bajtov (BSIZE je v xv6 definovaný na 1024). Tento limit je spôsobený tým, že inode v xv6 obsahuje 12 priamych blokových čísel a jedno nepriame blokové číslo, ktoré odkazuje na blok, ktorý obsahuje ďalších 256 blokových čísel, čo je spolu 12+256=268 blokov.

Program bigfile vytvára najväčšie možné súbory, a oznámi ich veľkosť:

Test zlyhá, pretože najväčší súbor má iba 268 blokov.

Súborový systém musíte zmeniť tak, aby podporoval dvojito nepriame bloky v každom inode, pričom každý bude obsahovať 256 adries nepriamych blokov, a tie budú obsahovať 256 adries dátových blokov. Celkovo teda bude možné ukladať súbory o veľkosti až 256*256+256+11 blokov (11 namiesto 12, lebo jeden blok sme obetovali na priame čísla blokov dvojito nepriameho bloku).

Predpoklady

mkfs inicializuje súborový systém, aby mal menej ako 2 000 voľných dátových blokov, čo je príliš nízky počet, aby ste mohli otestovať zmeny z tohoto cvičenia. Preto musíte zvýšiť túto hodnotu z 2 000 na 200 000 v súbore kernel/param.h:

Obnovte mkfs, aby vytvoril väčší disk:
$ rm mkfs/mkfs fs.img; make mkfs/mkfs

Na čo sa pozrieť

Formát diskového inodu je definovaný v struct dinode v súbore fs.h. Najviac vás budú zaujímať položky NDIRECT, NINDIRECT, MAXFILE, a addrs[] štruktúry struct dinode. Pozrite si tiež obrázok 7.3 z xv6 knižky, v ktorom je zobrazený štandardný inode z xv6.

Kód, ktorý hľadá dáta súboru na disku je vo funkcii bmap() v fs.c. Prezrite si ju, aby ste pochopili, čo robí. bmap() je volaná pri čítaní aj zápise do súboru. Počas zápisu bmap() alokuje dostatočný počet nových blokov podľa potreby, aby sa do nich zmestil obsah súboru a zároveň alokuje nepriamy blok, ak je potrebný na uloženie adries blokov.

bmap() pracuje s dvoma druhmi čísel blokov. Argument bn je „logické číslo bloku“ — číslo bloku v súbore relatívne k začiatku súboru. Čísla blokov v ip->addrs[] a argument bread() sú čísla blokov na disku. Funkcia bmap() teda mapuje logické čísla blokov súborov na čísla blokov na disku.

Vaša úloha

Upravte bmap(), aby implementoval „dvojito nepriame“ bloky spolu s priamymi a nepriamymi blokmi. Musíte použiť iba 11 priamych blokov namiesto 12, aby ste tam zmestili nový „dvojito nepriamy“ blok; nemôžete zmeniť veľkosť inodu na disku. Prvých 11 položiek ip->addrs[] by mali byť priame bloky; dvanásta bude nepriamy blok (podobne ako doteraz); trinásty bude nový dvojito nepriamy blok. Úloha je hotová, keď bigfile zapíše 65803 blokov a usertesty zbehnú úspešne:

bigfile je časovo náročný test, vyhraďte si minimálne minútu a pol na jeho zbehnutie.

Pomôcky:

  • Dobre si naštudujute funckiu bmap(). Zakreslite diagram vzťahov medzi ip->addrs[], nepriamym blokom, dvojito nepriamym blokom a nepriamymi blokmi na ktoré ukazuje; a dátovými blokmi. Ubezpečte sa, že rozumiete, prečo pridanie dvojito nepriameho bloku zväčší maximálnu veľkosť súboru o 256*256 blokov (v skutočnosti o jeden menej, pretože prídete o jeden priamy blok).
  • Uvažujte nad tým, ako budete indexovať (priraďovať logické číslo bloku) dvojito nepriamy blok a nepriame bloky, na ktoré ukazuje.
  • Ak zmeníte definíciu NDIRECT, pravdepodobne budete musieť zmeniť deklaráciu addrs[] v struct inode v súbore file.h. Presvedčte sa, že struct inode a struct dinode majú rovnaký počet položiek vo svojich poliach addrs[].
  • Ak zmeníte definíciu NDIRECT, nezabudnite vytvoriť nový fs.img, pretože mkfs používa konštantu NDIRECT na zostavenie súborového systému.
  • Ak sa váš súborový systém dostane do nekonzistentného stavu (trebárs pádom systému), vymažte fs.img (z Unixu, nie xv6). Zavolaním make potom zostavíte nový súborový systém.
  • Nezabudnite uvoľniť každý blok, ktorý ste čítali v bread() pomocou brelse().
  • Nepriame a dvojito nepriame bloky by ste mali alokovať len vtedy, keď sú potrebné, tak ako to bolo v pôdovodnej bmap().
  • Uistite sa, že itrunc uvoľní všetky bloky súboru, vrátane dvojito nepriamych blokov.

Voliteľná výzva: pridajte podporu pre trojito nepriame bloky.

Symbolické odkazy

V druhej časti cvičenia pridáte do xv6 podporu symbolických odkazov. Symbolické odkazy (známe aj ako mäkké odkazy) odkazujú na súbor jeho cestou; keď otvoríte symbolický odkaz, jadro vás nasmeruje na odkazovaný súbor. Symbolické odkazu sú veľmi podobné pevným odkazom. Rozdiel spočíva v tom, že pevné odkazy môžu ukazovať len na súbor, ktorý sa nachádza na tom istom disku (ukazujú na konkrétny inode), zatiaľ čo symbolické odkazy môžu ukazovať na iné diskové zariadenie. Aj keď xv6 nepodporuje viaceré zariadenia, implementácia tohoto systémového volania vám dovolí lepšie pochopiť ako funguje vyhľadávanie cesty.

Vaša úloha

Implementujte nové systémové volanie symlink(char *target, char *path), ktoré vytvorí nový symbolický odkaz na path, ktorý bude ukazovať na súbor target. Pre viac informácií si pozrite manuálovú stránku funkcie symlink. Na otestovanie pridajte do Makefile program symlinktest a spustite ho. Implementáciu máte korektnú, ak majú testy takýto výstup (vrátane úspešných usertestov:

Pomôcky:

  • Najprv vytvorte nové číslo systémového volania pre symlink, pridajte záznam do user/usys.pl, user/user.h, a definujte prázdnu funkciu sys_symlink().
  • Pridajte nový typ súboru (T_SYMLINK) do kernel/stat.h, ktorý bude reprezentovať symbolický odkaz.
  • Pridajte nový príznak (O_NOFOLLOW) do kernel/fcntl.h, ktorý môže byť použitý v systémovom volaní open. Všimnite si, že príznaky, ktoré používa open sa dajú kombinovať pomocou bitového operátora OR, takže váš nový príkaz by nemal prekrývať existujúce príznaky. Po tejto úprave bude možné skompilovať user/symlinktest.c, keď ho pridáte do Makefile.
  • Implementujte nové systémové volanie symlink(char *target, char *path), ktoré vytvorí nový symbolický odkaz na path, ktorý bude ukazovať na súbor target. Na úspešné vytvorenie odkazu nemusí cieľ existovať. Cestu k cieľu musíte niekde uložiť, napríklad do dátových blokov inodu.
  • Upravte systémové volanie open, aby správne obslúžilo situáciu, kedy meno súboru ukazuje na symbolický odkaz. Ak súbor neexistuje, open musí zlyhať. Keď proces nastaví príznak O_NOFOLLOW vo volaní open, open by mal otvoriť priamo symbolický odkaz (nie súbor, na ktorý symbolický odkaz ukazuje).
  • Ak súbor, na ktorý ukazuje symbolický odkaz je tiež symbolický odkaz, musíte ho rekurzívne nasledovať, až kým sa nedostanete k bežnému súboru. Ak sú odkazy cyklické, musíte vrátiť chybový kód. Nemusíte programovať detekciu cyklov, stačí ak to odhadnete hĺbkou rekurzie (napr. 10).
  • Iné systémové volania (napr. link a unlink) nemôžu nasledovať symbolické odkazy; tieto symbolické odkazy pracujú priamo so symbolickými odkazmi.
  • Nemusíte ošetriť prípad symbolických odkazov na priečinky

Týmto je cvičenie hotové. Zmeny môžete commitnúť do repozitára.

Uistite sa, že váš kód prechádza všetkými testami pomocou make grade.

Poďakovanie

Ďakujeme vyučujúcim predmetu CSEP551 (Jeseň 2019) na Univerzite vo Washingtone za cvičenie so symbolickým odkazom.