Programátori OS dokážu robiť všelijaké triky s pamäťovým hardvérom. Príkladom je lenivá alokácia na halde pre užívateľské programy. Aplikácie na xv6 si môžu vypýtať pamäť na halde od operačného systému pomocou systémového volania sbrk(). V jadre, ktoré vyvíjate, sbrk() alokuje fyzickú pamäť požadovanej veľkosti a namapuje ju do virtuálneho adresného priestoru procesu. Existujú však programy, ktoré takýmto spôsobom alokujú veľké množstvo pamäte, ale nikdy ho celé nepoužijú – napr. riedke polia (polia, v ktorých má väčšina prvkov nulovú hodnotu). Sofistikované jadra pre tento prípad alokujú pamäť lenivo. To znamená, že sbrk() nealokuje fyzickú pamäť – iba si zapamätá adresný rozsah, na ktorom proces očakáva alokovanú pamäť na halde. Keď proces prvýkrát pristúpi k stránke v tomto rozsahu, CPU vyvolá výpadok stránky, ktorý kernel obslúži alokáciou fyzickej pamäte, jej vynulovaním a a namapovaním. V tomto cvičení sa budeme venovať implementácii tohoto mechanizmu do xv6.
Než sa vrhnete do programovania, prečítajte si tretiu kapitolu „Page Tables“ z knižky o xv6 (ak ste tak predtým nevykonali).
Začneme prepnutím repozitára do vetvy lazy.
|
1 2 |
$ git fetch $ git checkout lazy |
kernel/vm.c. Vďaka nej sa vám bude systém ľahšie ladiť a lepšie pochopíte stránkovanie na architektúre RISC-V. Korektnú implementáciu môžete overiť tak, že ju zavoláte v súbore exec.c. Tým vypíšete tabuľku stránok prvého procesu; výstup by mal vyzerať takto:
|
1 2 3 4 5 6 7 8 9 10 |
page table 0x0000000087f6e000 ..0: pte 0x0000000021fda801 pa 0x0000000087f6a000 .. ..0: pte 0x0000000021fda401 pa 0x0000000087f69000 .. .. ..0: pte 0x0000000021fdac1f pa 0x0000000087f6b000 .. .. ..1: pte 0x0000000021fda00f pa 0x0000000087f68000 .. .. ..2: pte 0x0000000021fd9c1f pa 0x0000000087f67000 ..255: pte 0x0000000021fdb401 pa 0x0000000087f6d000 .. ..511: pte 0x0000000021fdb001 pa 0x0000000087f6c000 .. .. ..510: pte 0x0000000021fdd807 pa 0x0000000087f76000 .. .. ..511: pte 0x000000002000200b pa 0x0000000080008000 |
Prvý riadok obsahuje adresu argumentu funkcie vmprint. Riadky PTE obsahujú index PTE v danej tabuľke stránok, adresu pte a fyzickú adresu PTE. Výstup tiež signalizuje úroveň slovníka stránok: položky najvyššej úrovne sú označené .., o úroveň nižšie .. .. atď. Nevypisujte záznamy, ktoré nie sú namapované. V príklade vyššie sú v najvyššom slovníku stránok namapované záznamy 0 a 255. Záznam 0 má namapovaný iba index 0 a najnižšia úroveň pre tento index má namapované záznamy 0, 1 a 2.
Zopár pomôcok:
kernel/riscv.h a použite ich.
kernel/defs.h, aby ste ju mohli zavolať z exec.c.
sbrk()sbrk(n). Jeho implementáciu sys_sbrk() nájdete v súbore sysproc.c. Systémové volanie sbrk(n) zväčší pamäť procesu o n bajtov a vráti smerník na začiatok alokovaného regiónu (pôvodnú veľkosť, ak pamäť počítame od nuly). Vaša nová implementácia sbrk(n) iba navýši počítadlo veľkosti procesu (myproc()->sz) o n a vráti pôvodnú veľkosť. Novú pamäť nebude alokovať — volanie growproc() musíte odstrániť.
Teraz si skúste tipnúť, čo sa stane, ak po tejto modifikácii naštartujeme systém. Čo sa pokazí?
Ukončite stávky prosím!
Naštartujte xv6, do shellu napíšte echo hi. Mali by ste uvidieť niečo takéto:
|
1 2 3 4 5 6 |
init: starting sh $ echo hi usertrap(): unexpected scause 0x000000000000000f pid=3 sepc=0x0000000000001258 stval=0x0000000000004008 va=0x0000000000004000 pte=0x0000000000000000 panic: uvmunmap: not mapped |
Správa „usertrap(): …“ pochádza z užívateľskej trap obsluhy v trap.c. Ďalej vidíme, že takýto druh výnimky obsluha nepozná (unexpected scause). Uistite sa, že rozumiete prečo došlo k výpadku stránky. Hodnota „stval=0x0..04008“ nám napríklad hovorí, že virtuálna adresa, ktorá spôsobila výnimku je 0x4008.
trap.c, aby obslúžil výpadok stránky z užívateľského priestoru namapovaním novo-alokovanej stránky fyzickej pamäte na adresu výpadku. Po obsluhe zabezpečte návrat do užívateľského priestoru, aby mohol proces pokračovať vo vykonávaní. Obsluhu by ste mali napísať pred volaním printf, ktoré spôsobilo vyššie uvedený výpis. Riešenie je hotové, ak prejdete testami usertests.
Odporúčame vám začať opravením funkcie usertrap() v trap.c tak, aby ste mohli spustiť echo hi v shelli. Akonáhle sa vám to podarí, objavíte ďalšie problémy, ktoré budete musieť vyriešiť, aby usertests fungoval korektne. Nasledujú užitočné pomôcky.
usertrap() zavoláte r_scause() a ten vám vráti 13 alebo 15.
printf() v usertrap(), ktoré sme vyššie popisovali.
uvmalloc() vo vm.c. Tento kód používa aj sbrk() (cez growproc()). V riešení zavoláte dve funkcie: kalloc() a mappages().
PGROUNDDOWN(va).
uvmunmap() bude panikáriť; modifikujte ju tak, aby nevyvolala panic, ak nejaké stránky nie sú namapované.
kernel/kernel.asm a nájdite v ňom problémovú inštrukciu sepc.
proc.h (a spinlock.h).
Ak všetko dopadlo dobre, mali by ste dosiahnuť stav, v ktorom viete spustiť echo hi. V shelli by mal nastať aspoň jeden výpadok stránky (a po ňom lenivá alokácia), možno dva.
UsertestsKeď vám zbehne základ, opravte svoj kód tak, aby prešli všetky testy programu usertests:
sbrk() so zápornými argumentami.
sbrk().
fork() korektne.
sbrk() v systémovom volaní read alebo write, ale pamäť pre danú oblasť ešte nebola alokovaná.
kalloc() zlyhá počas obsluhy výpadku stránky, ukončite aktuálny proces.
Vaše riešenie je hotové, ak prejde testami lazytests a usertests:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
$ lazytests lazytests starting running test lazy alloc test lazy alloc: OK running test lazy unmap... usertrap(): ... test lazy unmap: OK running test out of memory usertrap(): ... test out of memory: OK ALL TESTS PASSED $ usertests ... ALL TESTS PASSED $ |
make grade, aby ste overili správnosť svojho riešenia.
Týmto je cvičenie ukončené. Svoje zmeny môžete commitnúť do repozitára.