8. 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 8 File system z xv6 knižky a preštudujte si príslušný kód.

Ak chcete pracovať s počítačmi v učebni, postupujte podľa sekcie Stiahnutie repozitára na cvičení na stránke Synchronizácia repozitára.

Vo svojom repozitári sa prepnite do vetvy fs:

Riešenia úloh z tohto cvičenia ukladajte do vetvy fs.

Veľké súbory (stredná)

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 i-uzol 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 vytvorí súbor s maximálnou možnou veľkosťou a túto veľkosť vypíše:

Test očakáva, že môže zapisovať súbory až do veľkosti 65803 blokov. Najväčší súbor, ktorý je možné vytvoriť v neupravenej xv6 má 268 blokov a preto test zlyhá.

Súborový systém musíte zmeniť tak, aby podporoval dvojito nepriame bloky v každom i-uzle, 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

Program mkfs vytvára súborový systém xv6 a určuje celkový počet blokov súborového systému; táto veľkosť je určená konštantou FSSIZE v súbore kernel/param.h. Jej hodnota pre tento lab je 200 000 blokov. Vo výstupe make si môžete všimnúť tento riadok:

Tento riadok popisuje súborový systém, ktorý program mkfs/mkfs vytvoril: má 70 metadátových blokov (bloky, ktoré popisujú samotný súborový systém) a 199 930 dátových blokov, čo je spolu 200 000blokov.
Ak by ste potrebovali obnoviť stav súborového systému, použite make clean, ktorý obnoví fs.img do pôvodného stavu.

Na čo sa pozrieť

Formát diskového i-uzla 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 8.3 z xv6 knižky, v ktorom je zobrazený štandardný i-uzol 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ť i-uzla 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 usertests -q zbehne ú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 funkciu bmap(). Zakreslite diagram vzťahov medzi ip->addrs[], nepriamym blokom, dvojito nepriamym blokom a nepriamymi blokmi na ktoré ukazuje; a dátovými blokmi. Mali by ste rozumieť tomu, 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 inodestruct 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 (napríklad 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ôvodnej bmap().
  • Uistite sa, že itrunc uvoľní všetky bloky súboru, vrátane dvojito nepriamych blokov.
  • usertests bude bežať dlhšie ako v predchádzajúcich laboch, pretože hodnota FSSIZE je v tomto labe väčšia a veľké súbory sú tým pádom objemnejšie.

Po úspešnom dokončení úlohy nezabudnite vytvoriť commit!

Symbolické odkazy (stredná)

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 alebo priečinok jeho cestou; keď otvoríte symbolický odkaz, jadro vyhľadá túto cestu. Symbolické odkazy sú podobné pevným odkazom. Rozdiel spočíva v tom, že pevné odkazy môžu ukazovať len na súbory nachádzajúce sa na tom istom disku, nemôžu ukazovať na priečinky, a sú viazané na konkrétny cieľový i-uzol. Symbolické odkazy ukazujú na nejakú cestu, ktorá môže, ale nemusí existovať. Implementácia tohto systémového volania vám umožní lepšie pochopiť, ako funguje vyhľadávanie cesty.

Neimplementujte podporu pre symbolické odkazy na priečinky. Jediné systémové volanie, ktoré musí rozoznať a prekladať symbolické odkazy je open().

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 úspechu usertests:

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() v súbore kernel/sysfile.c.
  • 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(target, path), ktoré vytvorí nový symbolický odkaz umiestnený 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 i-uzla. Návratová hodnota systémového volania symlink je v prípade úspechu nulová, v opačnom prípade -1 (podobne ako link a unlink).
  • 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 systémové volania pracujú priamo so symbolickými odkazmi.

Spustite príkaz make grade, aby ste overili správnosť svojho riešenia. Pri kontrole vašej úspešnosti berte do úvahy, že úlohu file snapshots ste neriešili. Po úspešnom dokončení úlohy nezabudnite vytvoriť commit! Aby ste prešli posledným testom time, musíte vytvoriť nový súbor time.txt, v ktorom uvediete počet hodín, ktorý ste strávili nad zadaním ako celé číslo. Na záver aj túto zmenu commitnite do repozitára. Týmto je cvičenie ukončené.


Poďakovanie

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