Xv6 a UNIX-ové nástroje

Toto cvičenie vás zoznámi s operačným systémom xv6 a jeho systémovými volaniami.

Synchronizácia s repozitárom

Na prvých troch cvičeniach musíte pracovať na školských počítačoch, aby ste si zvykli na prostredie, ktoré budete používať na všetkých troch testoch. Na prvom cvičení ste vytvorili vzdialený repozitár, ktorý si teraz musíte na virtuálku stiahnuť. Postupujte podľa pokynov na stránke Synchronizácia repozitára v sekcii Stiahnutie repozitára na cvičení.

Bootovanie xv6 (ľahká)

Aby ste mohli začať pracovať s xv6, musíte mať nainštalované všetky nástroje, vrátane operačného systému xv6. Ak používate nami poskytnutý virtuálny stroj, všetko je už pripravené a sťahovanie repozitára môžete preskočiť.

Prejdite do repozitára xv6:

$ cd xv6-labs-2025

1	$ cd xv6-labs-2025

Repozitár je nastavený tak, aby sa po naklonovaní automaticky prepol na vetvu util. Môžete si to overiť príkazom git status:

$ git status
On branch util
Your branch is up to date with 'origin/util'.

nothing to commit, working tree clean

$ git status

On branch util

Your branch is up to date with 'origin/util'.

nothing to commit, working tree clean

Repozitár xv6-labs-2025 sa trochu líši od systému xv6-riscv popísaného v sprievodnej knihe kurzu. Repozitár, ktorý ste práve naklonovali obsahuje niekoľko súborov naviac. Ak ste zvedaví, pozrite si históriu repozitára príkazom:

$ git log

$ git log

Súbory, ktoré budeme potrebovať na tomto a ďalších cvičeniach budú distribuované pomocou Gitu. Na každom cvičení prepnete repozitár na inú vetvu, ktorá obsahuje verziu xv6 špeciálne pripravenú pre dané cvičenie. Napríklad na vetvu util sa prepnete príkazom git switch util. Viac informácií o programe git nájdete v používateľskom manuáli. Git vám umožní zaznamenať zmeny, ktoré urobíte v kóde. Keď dokončíte jednu úlohu z cvičenia, svoje zmeny uložíte (commitnete) takto:

$ git add user/sleep.c Makefile
$ git commit -m 'feat: implement sleep'
Created commit 60d2135: feat: implement sleep
 2 files changed, 15 insertions(+), 0 deletions(-)
$

$ git add user/sleep.c Makefile

$ git commit -m 'feat: implement sleep'

Created commit 60d2135: feat: implement sleep

2 files changed, 15 insertions(+), 0 deletions(-)

Vysvetlenie: Príkazom git add sme pridali upravené/nové súbory, ktoré sa stanú súčasťou commitu. Príkazom git commit potom vyžiadame uskutočnenie commitu. Prepínačom -m môžete priamo v príkaze uviesť správu ku commitu. Bez prepínača je otvorený textový editor (nastavený v súbore ~/.gitconfig), v ktorom je možné správu upraviť. Pripomíname, že commity vo vašich repozitároch musia spĺňať náležitosti uvedené v špecifikácii Conventional Commits 1.0.0.

Svoje aktuálne zmeny môžete sledovať pomocou príkazu git diff. Týmto príkazom zobrazíte zmeny, ktoré ste urobili od posledného commitu a príkazom git diff origin/util zobrazíte všetky zmeny od stavu, v akom ste repozitár xv6-labs-2025 obdržali. origin/util uvedený v príkaze je názov vetvy, v ktorej sa nachádza pôvodný kód z MIT, ktorý ste si stiahli na začiatku cvičenia (origin štandardne označuje vzdialený repozitár, z ktorého sťahujete kód).

Riešenia úloh z tohto cvičenia ukladajte do vetvy util. Túto vetvu budeme kontrolovať v rámci priebežnej kontroly repozitárov.

Skompilujte a spustite xv6:

$ make qemu
riscv64-unknown-elf-gcc    -c -o kernel/entry.o kernel/entry.S
riscv64-unknown-elf-gcc -Wall -Werror -O -fno-omit-frame-pointer -ggdb -DSOL_UTIL -MD -mcmodel=medany -ffreestanding -fno-common -nostdlib -mno-relax -I. -fno-stack-protector -fno-pie -no-pie   -c -o kernel/start.o kernel/start.c
...
riscv64-unknown-elf-ld -z max-page-size=4096 -N -e main -Ttext 0 -o user/_zombie user/zombie.o user/ulib.o user/usys.o user/printf.o user/umalloc.o
riscv64-unknown-elf-objdump -S user/_zombie > user/zombie.asm
riscv64-unknown-elf-objdump -t user/_zombie | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$/d' > user/zombie.sym
mkfs/mkfs fs.img README  user/xargstest.sh user/_cat user/_echo user/_forktest user/_grep user/_init user/_kill user/_ln user/_ls user/_mkdir user/_rm user/_sh user/_stressfs user/_usertests user/_grind user/_wc user/_zombie
nmeta 46 (boot, super, log blocks 30 inode blocks 13, bitmap blocks 1) blocks 954 total 1000
balloc: first 591 blocks have been allocated
balloc: write bitmap block at sector 45
qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0

xv6 kernel is booting

hart 2 starting
hart 1 starting
init: starting sh
$

$ make qemu

riscv64-unknown-elf-gcc -c -o kernel/entry.o kernel/entry.S

riscv64-unknown-elf-gcc -Wall -Werror -O -fno-omit-frame-pointer -ggdb -DSOL_UTIL -MD -mcmodel=medany -ffreestanding -fno-common -nostdlib -mno-relax -I. -fno-stack-protector -fno-pie -no-pie -c -o kernel/start.o kernel/start.c

...

riscv64-unknown-elf-ld -z max-page-size=4096 -N -e main -Ttext 0 -o user/_zombie user/zombie.o user/ulib.o user/usys.o user/printf.o user/umalloc.o

riscv64-unknown-elf-objdump -S user/_zombie > user/zombie.asm

riscv64-unknown-elf-objdump -t user/_zombie | sed '1,/SYMBOL TABLE/d; s/ .* / /; /^$/d' > user/zombie.sym

mkfs/mkfs fs.img README user/xargstest.sh user/_cat user/_echo user/_forktest user/_grep user/_init user/_kill user/_ln user/_ls user/_mkdir user/_rm user/_sh user/_stressfs user/_usertests user/_grind user/_wc user/_zombie

nmeta 46 (boot, super, log blocks 30 inode blocks 13, bitmap blocks 1) blocks 954 total 1000

balloc: first 591 blocks have been allocated

balloc: write bitmap block at sector 45

qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0

xv6 kernel is booting

hart 2 starting

hart 1 starting

init: starting sh

Ak do príkazového riadka napíšete ls, mali by ste uvidieť podobný výstup:

$ ls
.              1 1 1024
..             1 1 1024
README         2 2 2227
xargstest.sh   2 3 93
cat            2 4 32864
echo           2 5 31720
forktest       2 6 15856
grep           2 7 36240
init           2 8 32216
kill           2 9 31680
ln             2 10 31504
ls             2 11 34808
mkdir          2 12 31736
rm             2 13 31720
sh             2 14 54168
stressfs       2 15 32608
usertests      2 16 178800
grind          2 17 47528
wc             2 18 33816
zombie         2 19 31080

$ ls

. 1 1 1024

.. 1 1 1024

README 2 2 2227

xargstest.sh 2 3 93

cat 2 4 32864

echo 2 5 31720

forktest 2 6 15856

grep 2 7 36240

init 2 8 32216

kill 2 9 31680

ln 2 10 31504

ls 2 11 34808

mkdir 2 12 31736

rm 2 13 31720

sh 2 14 54168

stressfs 2 15 32608

usertests 2 16 178800

grind 2 17 47528

wc 2 18 33816

zombie 2 19 31080

Tieto súbory vytvorí program mkfs počas inicializácie súborového systému; väčšina z nich sú programy, ktoré môžete spustiť. Pred chvíľou ste jeden z nich spustili: ls.

xv6 nemá príkaz ps, ale ak stlačíte Ctrl+P, jadro vypíše informácie o každom procese. Ak to vyskúšate teraz, uvidíte dva riadky: jeden pre init a druhý pre sh.

Na vypnutie qemu stlačte postupne: spolu Ctrl+A a potom samostatne X.

Hodnotenie

Svoje riešenie môžete otestovať hodnotiacim programom zavolaním make grade. V jeho výstupe zistíte, ktoré úlohy ste vyriešeili správne. Plný počet bodov však neznamená, že váš kód je bezchybný.

sleep (ľahká)

V tejto úlohe sa naučíte písať používateľské programy pre xv6 a vyskúšate si systémové volanie pause.

Implementujte UNIX-ový program sleep pre xv6; vaša implementácia programu sleep by sa mala pozastaviť na používateľom definovaný počet tikov. Jeden tik je definovaný jadrom xv6 ako čas medzi dvoma prerušeniami časovacieho čipu. Svoje riešenie uložte do user/sleep.c.

Pomôcky:

Než začnete programovať, prečítajte si kapitolu 1 z xv6 knižky.
Pozrite sa na zdrojový kód iných programov v priečinku user/ (napr. user/echo.c, user/grep.c, a user/rm.c), aby ste zistili ako načítať argumenty príkazového riadku zadané pri spustení programu.
Ak používateľ zabudne uviesť argument, sleep by mal vypísať chybovú hlášku.
Argument príkazového riadku je reťazec; na celé číslo ho môžete skonvertovať pomocou funkcie atoi() (viď user/ulib.c).
Použite systémové volanie pause().
Užitočné časti zdrojového kódu nájdete v týchto súboroch:

kernel/sysproc.c

implementácia systémového volania pause() (hľadajte sys_pause())

user/user.h

definícia volania pause() z používateľského programu

user/usys.S

kód assembly, ktorý prechádza z používateľského módu do módu jadra
Pridajte svoj program sleep do premennej UPROGS v súbore Makefile. Keď to máte hotové, príkazom make qemu skompilujete program a môžete ho spustiť z xv6 shellu.
Na vylepšenie zručností v programovacom jazyku C si prečítajte knižku Programovací jazyk C (v origináli The C programming language) od Kernighana a Ritchieho. Ak radi sledujete video tutoriály, pozrite si opakovanie jazyka C od vášho kolegu Mariána Šebeňu.

Spustite program z xv6 shellu:

$ make qemu
...
init: starting sh
$ sleep 10
(chvíľu sa nič nebude diať)
$

$ make qemu

...

init: starting sh

$ sleep 10

(chvíľu sa nič nebude diať)

Váš program by sa mal pozastaviť. Spustite make grade (v príkazovom riadku mimo qemu), aby ste zistili, či program sleep prejde všetkými testami.

make grade spúšťa všetky testy, aj pre úlohy, ktoré ešte nemáte vypracované. Ak chcete spustiť testy len pre jednu úlohu, napíšte:

$ ./grade-lab-util sleep

1	$ ./grade-lab-util sleep

Týmto spustíte testy, ktoré v názve obsahujú „sleep“. Iný spôsob:

$ make GRADEFLAGS=sleep grade

1	$ make GRADEFLAGS=sleep grade

urobí to isté.

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

sixfive (stredná)

V tomto cvičení použijete systémové volania open a read, reťazce a spracovanie textových súborov v jazyku C.

Pre každý vstupný súbor program sixfive vypíše všetky čísla v súbore, ktoré sú násobkami 5 alebo 6. Čísla sú v súbore uložené ako postupnosti číslic oddelené znakmi z reťazca " -\r\t\n./,". Napríklad číslo 6 z reťazca "xv6" sa nevypíše, ale z reťazca "/6," sa vypíše.

Nasledujúci príklad ilustruje správanie programu sixfive:

$ sixfive sixfive.txt
5
100
18
6
$

$ sixfive sixfive.txt

100

Pomôcky:

Vstupný súbor čítajte znak po znaku.
Či znak zodpovedá niektorému z oddeľovačov v reťazci môžete otestovať pomocou funkcie strchr() (viď user/ulib.c).
Začiatok a koniec súboru berte ako oddeľovače.

memdump (ľahká)

V tejto úlohe získate viac praxe so smerníkmi v jazyku C. Než sa pustíte do programovania, prečítajte si sekcie Pred začiatkom si prečítajte sekcie 5.1 (Pointers and addresses) až 5.6 (Pointer arrays) a 6.4 (pointers to structures) z knižky The C programming language) od Kernighana a Ritchieho.

Otvorte si user/memdump.c. Vašou úlohou je implementovať funkciu memdump(char *fmt, char *data). Účelom memdump() je vypísať obsah pamäte, na ktorú ukazuje smerník data vo formáte určenom argumentom fmt. Konkrétny formát je určený reťazcom. Každý znak tohto reťazca určuje, ako sa má vypísať časť dát (v danom poradí). Napríklad štruktúra s viacerými položkami sa dá vypísať pomocou formátovacieho reťazca s viacerými znakmi.

Vaša implementácia funkcia funkcie memdump() by mala podporovať tieto formátovacie znaky:

i: vypíše nasledujúce 4 bajty dát ako 32-bitové celé číslo v desiatkovej sústave.
p: vypíše nasledujúcich 8 bajtov dát ako 64-bitové celé číslo v šestnástkovej sústave.
h: vypíše nasledujúce 2 bajty dát ako 16-bitové celé číslo v desiatkovej sústave.
c: vypíše 1 bajt dát ako 8-bitový ASCII znak.
s: nasledujúcich 8 bajtov dát obsahuje 64-bitový smerník na reťazec; vypíše tento reťazec.
S: zvyšné dáta obsahujú štandardný reťazec ukončený nulou; vypíše tento reťazec.

Môžete použiť funkciu printf().

Ak program memdump spustíte bez argumentov, zavolá funkciu memdump() s niekoľkými ukážkovými formátmi. Ak je memdump() správne implementovaná, výstup bude:

$ memdump
Example 1:
61810
2025
Example 2:
a string
Example 3:
another
Example 4:
BD0
1819438967
100
z
xyzzy
Example 5:
hello
w
o
r
l
d

$ memdump

Example 1:

61810

2025

Example 2:

a string

Example 3:

another

Example 4:

BD0

1819438967

100

xyzzy

Example 5:

hello

Hexadecimálna adresa v prvom riadku príkladu 4 bude vo vašom výstupe iná.

Ak program memdump spustíte s argumentom, načíta štandardný vstup a použije ho ako dáta a argument použije ako formátovací reťazec. Výstup pri korektnej implementácii:

$ echo deadc0de | memdump hhcccc
25956
25697
c
0
d
e
$ echo deadc0de | memdump p
64616564
$

$ echo deadc0de | memdump hhcccc

25956

25697

$ echo deadc0de | memdump p

64616564

Implementujte memdump().

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.

Voliteľné úlohy

Prvý riešiteľ každej úlohy môže dostať bonusové body po kontrole riešenia. Informujte sa u prednášajúceho alebo cvičiaceho. Voliteľné úlohy môžete riešiť až po vyriešení všetkých úloh základnej časti cvičenia! Riešenia prijímame iba do konca tretieho týždňa semestra.

Shell xv6 (user/sh.c) je iba ďalší používateľský program. Chýba v ňom veľa funkcií, ktoré nájdete v skutočných shelloch. Môžete ho modifikovať a vylepšiť. Tu je niekoľko funkcionalít, ktoré do shellu môžete pridať:
- Upravte shell tak, aby nevypisoval $ počas spracovania príkazov zo súboru. (stredná)
- Implementujte podporu wait. (ľahká)
- Pridajte podporu dopĺňania tabulátorom. (ľahká)
- Upravte shell, aby udržoval históriu predchádzajúcich volaných príkazov. (stredná)
Alebo implementujte hocijakú inú funkcionalitu, ktorú chcete, aby váš shell podporoval. (Ak sa cítite dobrodružne, môžete pridať do jadro systému funkcionality, ktoré potrebujete; samotný xv6 toho veľa nepodporuje.)

2. cvičenie – utility