3. cvičenie – tabuľky stránok

Tabuľky stránok

V tomto cvičení preskúmate tabuľky stránok a upravíte ich za účelom zrýchlenia určitých systémových volaní a detekcie stránok, kuk ktorým proces pristúpil.

Než začnete programovať, prečítajte si kapitolu 3 xv6 knižky a pozrite si príslušné súbory:

  • V kernel/memlayout.h je znázornené usporiadanie pamäte.
  • kernel/vm.c obsahuje väčšinu kódu, ktorý pracuje s virtuánou pamäťou (VM).
  • kernel/kalloc.c obsahuje kód na alokáciu a uvoľnovanie fyzickej pamäte.

Nápomocný môže byť tiež manuál privilegovaných inštrukcií RISC-V.

Najprv sa prepnite do vetvy pgtbl:

Riešenia úloh z tohto cvičenia ukladajte do vetvy pgtbl. Túto vetvu budeme kontrolovať v rámci priebežnej kontroly repozitárov. Viac informácií k hodnoteniu repozitárov nájdete na príslušnej stránke.

Zrýchlenie systémových volaní (ľahká)

Niektoré operačné systémy (napr. Linux) zrýchľujú určité systémové volania zdieľaním dát medzi jadrom a užívateľským priestorom v pamäťovej oblasti s prístupom iba na čítanie. Vďaka tomu je možné eliminovať prechody do jadra počas systémových volaní. Aby ste sa naučili, ako fungujú pamäťové mapovania, vašou prvou úlohou je implementovať túto optimizáciu pre systémové volaniegetpid() v xv6.

Vždy, keď je vytvorený nový proces, namapujte jednu stránku na čítanie na adresu USYSCALL (táto virtuálna adresa je definovaná v súbore memlayout.h). Na začiatku tejto stránky uložte štruktúru struct usyscall (tiež definovaná v memlayout.h) a inicializujte ju tak, aby v nej bolo uložené PID aktuálneho procesu. Pre tento lab je z užívateľského priestoru k dispozícii funkcia ugetpid(), ktorá automaticky použije mapovanie USYSCALL. Za implementáciu tejto úlohy získate plný počet bodov, ak prejdete testom ugetpid v súbore testov pgtbltest.

Pomôcky:

  • Nezabudnite alokovať a inicializovať stránku vo funkcii allocproc(). Vhodné je tiež niekam uložiť referenciu na alokovanú stránku, napríklad do štruktúry proc, podobne ako sa ukladá proc->trapframe a proc->pagetable.
  • Mapovanie môžete nastaviť vo funkcii proc_pagetable() v súbore kernel/proc.c.
  • Nastavte správne príznaky, aby bola stránka z užívateľského priestoru len na čítanie.
  • Funkcia mappages() sa vám môže hodiť.
  • Nezabudnite stránku uvoľniť vo funkcii freeproc() a odmapovať v proc_freepagetable().

Ktoré iné systémové volania môžu byť urýchlené prostredníctvom tejto zdieľanej stránky? Vysvetlite ako.

Odpovede zapíšte do príslušných súborov podľa testovacieho skriptu.

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

Vypísanie tabuľky stránok (ľahká)

Vašou druhou úohou je napísať funkciu, ktorá vypíše obsah tabuľky stránok. Pomôže vám to pri vizualizícii tabuliek stránok v RISC-V a funkciu môžete v budúcnosti použiť pri ladení systému.

Definujte funkciu vmprint(). Bude mať jeden argument typu pagetable_t a vypíše tabuľku stránok vo formáte, ktorý je uvedený nižšie. Funkciu môžete otestovať napríkad tak, že ju zavoláte v súbore exec.c tesne pred return argc. Aby bola tabuľka vypísaná len pre prvý proces, skontrolujte číso procesu: if(p->pid==1) vmprint(p->pagetable). Plný počet bodov za túto úlohu dostanete, ak prejdete testom pte printout.

Keď spustíte xv6, mali by ste vidieť podobný výstup. Ak ste funkciu zavolali vyššie popísaným spôsobom, jedná sa o stav tabuľky prvého procesu (init) tesne pred jeho spustením v systémovom volaní exec.

V prvom riadku je argument funkcie vmprint. Potom nasledujú riadky pre každý PTE, vrátane vnorených záznamov. Každý riadok PTE je odsadený znakmi .. podľa toho, ako hboko v strome sa nachádza. Každý riadok obsahuje index záznamu, bity pte a fyzickú adresu vytiahnutú z PTE. Nevypisujte neplatné záznamy. V príklade vyššie má tabuľka najvyššej úrovne mapovania pre záznamy 0 a 255. O úroveň nižšie, záznam 0 má namapovaný len index 0. Na najnižšej úrovni má tento index namapované záznamy 0, 1, 2 a 3.

Fyzické adresy na vašom počítači môžu byť odlišné od tých v ukážke výstupu. Počet záznamov a virtuálne adresy by mali byť rovnaké.

Pomôcky:

  • vmprint() môžete definovať v kernel/vm.c.
  • Použite makrá na konci súboru kernel/riscv.h.
  • Inšpirujte sa funkciou freewalk().
  • Deklaráciu funkcie vmprint() dajte do kernel/defs.h, aby ste ju mohi zavolať z exec.c.
  • Použite formátovaciu značku %p na výpis PTE a adries ako 64-bitové hexadecimálne číslo.

Vysvetlite výstup funkcie vmprint() a jeho súvis s obrázkom 3.4 z xv6 knižky. Čo obsahuje stránka 0? Čo je v stránke 3? Keď proces beží v užívateľskom móde, môže prečítať/zapísať pamäť mapovanú stránkou 2? Čo obsahuje tretia stránka od konca?

Odpovede zapíšte do príslušných súborov podľa testovacieho skriptu.

Detekcia prístupu k stránkam (ťažká)

Niektorým garbage collectorom (forma automatickej správy pamäte) môže byť užitočná informácia o tom, ku ktorým stránkam bol v minulosti uskutočnený prístup (čítanie alebo zápis). V tejto časti cvičenia budete implementovať do xv6 novú funkcionalitu, ktorá deteguje a ohlási túto informáciu užívateľskému priestoru preskúmaním prístupových bitov v tabuľke stránok architektúry RISC-V. Hardvér tejto architektúry nastavuje tieto bity v PTE vždy, keď fyzickú adresu stránky nenájde v TLB cache.

Vašou úlohou je implementovať systémové volanie pgaccess(), ktoré oznámi stránky, ku ktorým bol v minulosti vykonaný prístup. Toto systémové volanie má tri argumenty. Prvý je virtuálna adresa začiatku stránky, ktorú má prvú skontrolovať. Druhý je počet stránok, ktoré má skontrolovať. Tretí je užívateľská adresa pamäte, kde bude výsledok zapísaný vo forme bitovej masky (dátová štruktúra, ktorá používa jeden bit na stránku a prvú stránku reprezentuje najmenej významný bit). Za túto úlohu dostanete plný počet bodov, ak prejdete testom pgaccess v súbore testov pgtbltest.

Pomôcky:

  • Prečítajte si funkciu pgaccess_test() v súbore user/pgtlbtest.c, aby ste videli, ako sa volanie pgaccess používa.
  • Najprv implementujte funkciu sys_pgaccess() v súbore kernel/sysproc.c.
  • Argumenty parsujte pomocou argaddr() a argint().
  • Čo sa týka výstupnej masky, je jednoduchšie použiť dočasný buffer v jadre a skopírovať ho užívateľovi (pomocou copyout()) potom, ako ho naplníte správnymi bitmi. Nezabudnite skopírovať len toľko dát, koľko si užívateľ vyžiadal (zaokrúhlené na bajty).
  • Je v poriadku, ak obmedzíte maximálny počet stránok, ktorý je možné skenovať.
  • Funkcia walk() v súbore kernel/vm.c je veľmi užitočná na hľadanie správnych PTE.
  • Prístupový bit PTE_A musíte definovať v súbore kernel/riscv.h. Nahliadnite do tretej kapitoly xv6 knižky, aby ste zistili jeho hodnotu. Môžete použiť tiež manuál privilegovaných inštrukcií RISC-V.
  • Po kontrole hodnoty PTE_A ju nezabudnite vynulovať, ak bola nastavená. V opačnom prípade nebudete vedieť zistiť, či bolo k stránke pristúpené od posledného volania pgaccess() (inými slovami, bit bude navždy nastavený).
  • Funkcia vmprint() sa vám môže hodiť pri ladení.

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

Týmto je cvičenie hotové. Skontrolujte, či vaše riešenie prejde všetkými testami make grade. 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 nezabudnite aj túto zmenu commitnúť do repozitára.

make grade môže zlyhať aj v prípade, že testy osamote zbehnú v poriadku. Je to spôsobené časovým limitom testov. Môžete ho zvýšiť v príslušnom súbore grade-lab-pgtbl (parametre timeout). Časový limit zmeňte iba v takom prípade, že viete, že samotný test zbehne v poriadku a nič iné v súbore neupravujte.

Pre úspešné testovanie je potrebné použiť aspoň 3 jadrá vo VirtualBoxe.

Voliteľné úlohy

  • Použite super-stránky (super-pages), aby ste zmenšili počet PTE v tabuľkách stránok.
  • Odmapujte prvú stránku užívateľského procesu, aby dereferencia nulového smerníka viedla k výpadku stránky. Musíte zmeniť súbor user.ld, aby užívateľský segment text začínal napríklad na adrese 4096 namiesto 0.
  • Pridajte systémové volanie, ktoré vracia špinavé (modifikované) stránky prostredníctvom príznaku PTE_D.