[OSy] Zadani 2. semestralky
Martin Decky
decky at dsrg.mff.cuni.cz
Mon Oct 15 01:32:14 CEST 2007
Hezke rano,
na konci tohoto emailu se nachazi zadani 2. semestralni prace. Zakladni
instrukce k vypracovani jsou shodne se zadanim 1. semestralni prace.
Definitivni slozeni skupin, rozdeleni rozsirenych zadani a vytvoreni pristupu
do SVN bude doreseno v prubehu nasledujicich dnu.
Take u 2. semestralni prace bude platit, ze priblizne 3 tydny pred datem
odevzdani zakladniho zadani obdrzite testy, pomoci nichz budeme testovat
spravnost Vaseho reseni v ramci zakladniho zadani (a budou take slouzit jako
pomocne kriterium pri hodnoceni rozsireneho zadani).
Na zaver pripominam nekolik dulezitych informaci:
* Odevzdani zakladniho zadani 1. semestralky probehne 2. 12. Zcela presne
budeme testovat, zda projde testy zakladniho zadani revize s casovym
razitkem 3. 12. 2007 00:00 CET.
* Pokud Vase reseni neprojde testy nebo o to explicitne pozadate, pobezi Vam
od 3. 12. lhuta 7 dnu na opozdene odevzdani s penalizaci 1/10 z maximalniho
mozneho poctu bodu. Pri odevzdani pozdeji nez 9. 12. jiz nebudete moci
ziskat zapocet.
Hodne stesti!
M.D.
Zadani 2. semestralni prace: -------------------------------------------------
Cilem 2. semestralni prace je rozsirit jadro z 1. semestralni prace
o spravu fyzicke pameti a mapovani virtualni pameti do fyzicke. Zadani ma
formu rozhrani, ktere je nutno naimplementovat. K zajisteni rozumne urovne
funkcnosti je nutne, aby implementace prosla sadou testu, ktere overuji
jeji funkcnost.
Ukolem bude naprogramovat:
* alokator fyzickych stranek pameti
* alokator oblasti virtualni pameti
* mapovani virtualni pameti do fyzicke
* pristup vlaken do virtualniho adresoveho prostoru
* obsluhu vyjimek TLB
Pokud zadani nespecifikuje nejaky detail, je zavazne chovani, ktere
ocekavaji testy. Pokud testy dane chovani netestuji, zadani si podle
uvazeni dodefinujte a sve rozhodnuti zdokumentujte.
Obecne pozadavky tykajici se deklarace a pouzivani chybovych kodu,
definice zakladnich typu pouzivanych v zadani a pozadavky na formu
zdrojovych textu jsou shodne se zadanim 1. semestralni prace.
Virtualni adresovy prostor procesoru
------------------------------------
V zavislosti na aktualnim rezimu (user, supervisor, kernel) je virtualni
adresovy prostor procesoru MIPS R4000 rozdelen na nekolik segmentu.
V uzivatelskem rezimu (user mode) je pristupny pouze segment USEG
v rozsahu adres [0x00000000,0x800000000), ktery je mapovany do fyzicke
pameti pres TLB. Pristup na adresu mimo USEG vyvola vyjimku Address
Error.
V rezimu supervizora (supervisor mode) jsou definovany segmenty SUSEG
v rozsahu adres [0x00000000,0x80000000), a segment SSEG v rozsahu adres
[0xC0000000,0xE00000000). Adresy v obou segmentech jsou mapovany do
fyzicke pameti pres TLB, pricemz segment SUSEG je analogii segmentu USEG
v uzivatelskem rezimu. Pristup na adresy mimo SUSEG a SSEG vyvola
vyjimku Address Error.
A konecne v rezimu jadra (kernel mode) jsou definovany segmenty KUSEG
v rozsahu adres [0x00000000,0x80000000), KSEG0 v rozsahu adres
[0x80000000,0xA0000000), KSEG1 v rozsahu adres [0xA0000000,0xC0000000),
KSSEG/KSEG2 v rozsahu adres [0xC0000000,0xE0000000) a KSEG3 v rozsahu
adres [0xE0000000,0xFFFFFFFF]. Adresy v segmentech KUSEG, KSSEG a KSEG3
jsou mapovany do fyzicke pameti pres TLB, pricemz segmenty KUSEG resp.
KSSEG jsou analogii segmetu USEG resp. SSEG v uzivatelskem rezimu resp.
rezimu supervizora. Adresy v segmentech KSEG0 a KSEG1 jsou mapovany do
fyzicke pameti primo (pouze odectenim pocatecni adresy segmentu).
Virtualni adresy segmentu KSEG0 jsou tedy mapovany na fyzicke adresy
v rozsahu [0x00000000,0x20000000), podobne je to i v pripade KSEG1.
Na realnem systemu se segmenty KSEG0 a KSEG1 lisi take v tom, ze
pristup na adresy KSEG0 obchazi cache procesoru.
Virtualni adresovy prostor procesu
----------------------------------
V kontextu operacniho systemu je virtualni adresovy prostor procesu,
nebo take mapa virtualni pameti (address space, virtual memory map, vmm),
datova struktura, ktera udrzuje informace o vyuziti adresoveho prostoru.
Rozdeleni virtualniho adresoveho prostoru procesoru na segmenty je
pevne dane. Protoze se zpracovani virtualnich adres procesorem
v jednotlivych segmentech lisi, je virtualni adresovy prostor procesu
typicky alokovan po oblastech (virtual memory area, vma) uvnitr techto
segmentu. Oblasti virtualni pameti reprezentuji souvisly blok adres ve
virtualnim adresovem prostoru. V zavislosti na tom, v jakem segmentu
adresoveho prostoru procesoru se urcita oblast nachazi, je pak mapovani
rozsahu virtualnich adres oblasti do fyzicke pameti bud pevne dane
(pripad segmentu KSEG0 a KSEG1) nebo definovane uzivatelem (operacnim
systemem), ktery ma moznost ovlivnovat obsah TLB.
Virtualni adresovy prostor procesu je jednim z prostredku sdilenych
vlakny uzivatelskeho procesu. Z bezpecnostnich duvodu ma kazdy proces
operacniho systemu svuj vlastni virtualni adresovy prostor a tedy i
mapovani do fyzicke pameti.
Kostra kernelu z 1. semestralni prace dosud pracuje pouze s nezavislymi
vlakny, ktere bezi v rezimu jadra. Pro nasledny prechod k procesum
s vice vlakny bezicimi v uzivatelskem rezimu (napln 3. semestralni
prace) je ovsem nejprve nutne vytvorit podporu pro virtualizaci pameti,
jeji mapovani do fyzicke pameti a sdileni tohoto mapovani vlakny.
Zakladni zadani ------------------------------------------------------------
Alokator fyzicke pameti
-----------------------
Implementujte spravu fyzickych stranek (ramcu) pameti pro evidenci,
ktere fyzicke stranky jsou jiz pouzity a ktere jsou stale volne.
Pro spravu fyzicke pameti pouzijte vhodnou datovou strukturu, pricemz
duraz je kladen na rozumne rychle nalezeni volnych fyzickych stranek.
* void *frame_alloc(unsigned int cnt, unsigned int flags)
Funkce nalezne a alokuje @cnt po sobe jdoucich volnych fyzickych
stranek pameti. V pripade, ze je @cnt vetsi nez nula a alokace je
uspesna, vraci fyzickou adresu prvni naalokovane fyzicke stranky.
V opacnem pripade vraci hodnotu NULL (predpoklada se, fyzicka stranka
0 je jiz pouzivana kernelem).
Za volne fyzicke stranky se povazuji pouze ty, ktere lze bez omezeni
pouzit, neobsahuji tedy staticky alokovanou pamet (kod a data jadra,
struktury alokatoru apod.) nebo fyzicke stranky drive alokovane
volanim funkce frame_alloc() a dosud neuvolnene.
Pokud je v bitovem poli VF_ADDR_TYPE v argumentu @flags hodnota
VF_AT_KSEG0 resp. VF_AT_KSEG1, alokace se uvazuje jen v te casti
fyzicke pameti, ktera je pristupna ze segmentu KSEG0 resp. KSEG1
virtualniho adresniho prostoru, tedy v rozsahu fyzickych adres
[0x00000000,0x20000000). Naopak hodnoty VF_AT_KUSEG, VF_AT_KSSEG
a VF_AT_KSEG3 oznacuji moznost prednostne alokovat fyzicke stranky
mimo tento rozsah (jsou-li k dispozici), aby nedochazelo ke zbytecnemu
plytvani fyzickych stranek pristupnych z KSEG0 resp. KSEG1.
Binarni format argumentu @flags je dan makry VF_AT_SIZE a VF_AT_SHIFT,
ktere specifikuji velikost bitoveho pole a jeho pozici ve slove.
* int frame_free(void *paddr, unsigned int cnt)
Uvolneni @cnt po sobe jdoucich fyzickych stranek zacinajicich na
fyzicke adrese @paddr. Uvolnit lze pouze fyzicke stranky, ktere byly
drive alokovany funkci frame_alloc(), tedy nikoliv staticky alokovanou
pamet pro kod a data jadra, struktury alokatoru apod.
Je pripustne, aby bylo nejprve pomoci jedineho volani funkce
frame_alloc() naalokovano nekolik fyzickych stranek a podintervaly
techto fyzickych stranek byly pote jednotlive uvolnovany opakovanym
volanim frame_free(). Podobne je mozne pomoci frame_free() uvolnit
interval fyzickych stranek, ktery byl naalokovan vice nez jednim
volanim frame_alloc().
Funkce vraci EOK, bylo-li uvolneni uspesne, nebo EINVAL, pokud @cnt je
rovno nule, @paddr neobsahuje fyzickou adresu zarovnanou na pocatek
fyzicke stranky nebo posloupnost @cnt po sobe jdoucich fyzickych stranek
neni alokovana pomoci frame_alloc().
Uprava stavajiciho alokatoru pameti
-----------------------------------
Stavajici alokator pameti s rozhranim malloc/free alokuje pamet z haldy
umistene v segmentu KSEG0 virtualniho adresoveho prostoru procesoru.
Protoze soucasne s timto alokatorem bude stranky fyzicke pameti alokovat
take volani frame_alloc(), je nutne zajistit, aby alokator haldy
pouzival jen fyzicke stranky pameti pridelene pomoci frame_alloc().
Upravte stavajici alokator tak, aby pouzival rozhrani
frame_alloc/frame_free a zaroven aby vracel pouze pamet ze segmentu
KSEG0 virtualniho adresoveho prostoru procesoru, tj. aby bylo mozne
k alokovane pameti pristupovat bez pouziti TLB.
Pristup vlaken do virtualniho adresoveho prostoru
-------------------------------------------------
Rozsirte stavajici implementaci vlaken v jadre o podporu pristupu
k virtualni pameti mapovane pres TLB v ramci virtualniho adresoveho
prostoru.
Pro ucely testovani rozsirte chovani funkce thread_create() ze zadani
1. semestralni prace:
* int thread_create(
thread_t *thread_ptr, void (*thread_start)(void *), void *data,
unsigned int flags)
Pokud bude argument @flags obsahovat priznak TF_NEW_VMM, pro nove
vytvorene vlakno bude take vytvoren novy virtualni adresovy prostor.
Nove vlakno tedy nebude sdilet mapovanou virtualni pamet s volajicim
vlaknem.
Sprava virtualniho adresniho prostoru
-------------------------------------
Sprava oblasti virtualni pameti zahrnuje alokaci, manipulaci a
uvolnovani oblasti virtualni pameti v kontextu virtualniho adresoveho
prostoru prave beziciho vlakna. V ramci zakladniho zadani sestava
virtualni adresovy prostor z nejvyse MAX_AREAS souvislych oblasti.
Oblasti se nesmi prekryvat, velikost a zacatek oblasti musi byt
zarovnan na nejmensi velikost stranky podporovanou procesorem,
v pripade MIPS R4000 tedy 4 KiB.
Konstantu MAX_AREAS vhodne urcete tak, aby vyhovovala zamyslenym
pozadavkum vlaken na alokaci oblasti virtualni pameti. V ramci
zakladniho zadani je pripustne pro reprezentaci virtualniho adresoveho
prostoru pouzit staticky alokovane datove struktury, tedy datove
struktury napevno dimenzovane na MAX_AREAS oblasti virtualni pameti.
* int vma_alloc(
void **from, const size_t size, const unsigned int flags)
Funkce alokuje oblast ve virtualnim adresovem prostoru o velikosti
@size bajtu, pro tuto oblast alokuje fyzickou pamet a vytvori mapovani
prave alokovane virtualni pameti do fyzicke.
V zavislosti na hodnote bitoveho priznaku VF_VIRT_ADDR v argumentu
@flags funkce bud automaticky zvoli vhodnou adresu zacatku oblasti
virtualni pameti a vrati ji ve @from (hodnota VF_VA_AUTO), nebo se
pokusi vytvorit oblast na adrese zadane volajicim ve @from (hodnota
VF_VA_USER).
Bitove pole VF_ADDR_TYPE v argumentu @flags urcuje typ segmentu
virtualniho adresoveho procesoru, ve kterem bude virtualni oblast
alokovana. Hodnoty bitoveho pole pro jednotlive segmenty jsou
VF_AT_KUSEG, VF_AT_KSEG0, VF_AT_KSEG1, VF_AT_KSSEG a VF_AT_KSEG3.
Alokace v segmentech KSEG0 a KSEG1 se vzajemne vylucuji, pokud jsou
mapovany na stejne fyzicke adresy.
Binarni format argumentu @flags je dan makry VF_VA_SIZE, VF_VA_SHIFT
a VF_AT_SIZE, VF_AT_SHIFT, ktere specifikuji velikost bitoveho pole
a jeho pozici ve slove.
Vraci EOK pokud byla pamet alokovana a namapovana, EINVAL pokud
nebylo mozne alokovat oblast se zacatkem na adrese @from v danem
segmentu virtualniho adresoveho prostoru procesoru, nebo pokud
@from ci @size nejsou zarovnany, ENOMEM pokud neni dostatek fyzicke
pameti k provedeni operace nebo jiz bylo dosazeno MAX_AREAS oblasti
virtualni pameti.
* int vma_free(void *from)
Funkce zrusi mapovani pameti pro oblast se zacatkem na adrese @from,
ktera byla predtim vytvorena volanim vma_alloc(). Dale uvolni fyzickou
pamet, do ktere byla oblast mapovana a zrusi prislusnou oblast
virtualni pameti.
Vraci EOK pokud byla pamet uvolnena a mapovani zruseno, EINVAL pokud
@from neukazuje na zacatek oblasti vytvorene volanim vma_alloc().
Obsluha vyjimek TLB
-------------------
Pri prekladu virtualni adresy na fyzickou muze procesor vyvolat dva
druhy vyjimek. Prvni z vyjimek je TLB Refill, ktera je vyvolana
v pripade, ze pro pozadovanou virtualni adresu nebyl v TLB nalezen
zaznam s odpovidajici fyzickou adresou. Druhou z vyjimek je TLB Invalid,
ktera je vyvolana v pripade, ze v TLB sice existuje polozka pro
pozadovanou virtualni adresu, ale tato polozka je neplatna.
Obsluha obou typu vyjimek by mela nalezt mapovani pro prislusnou virtualni
adresu a naplnit TLB. Pokud nebude pro danou virtualni adresu mapovani
existovat, ocekava se, ze jadro vypise varovne hlaseni a vlakno, ktere
vyjimku vyvolalo, zrusi.
Pozn.: Moznost oznacit polozku TLB jako neplatnou lze pouzit napr. pri
implementaci copy-on-write mechanizmu nebo swapovani, v ramci zadani 2.
semestralni prace vsak pro jeho vyuziti neni prostor.
Kopirovani pameti mezi vlakny
-----------------------------
Pro testovaci ucely implementujte nasledujici funkce:
* int copy_from_thread(thread_t thr,
void *dest, const void *src, const size_t len)
Funkce zkopiruje data z virtualni pameti vlakna @thr do virtualni
pameti volajiciho vlakna. Vraci EOK pokud byla data zkopirovana,
EINVAL pokud je identifikace zdrojoveho vlakna neplatna.
* int copy_to_thread(thread_t thr,
void *dest, const void *src, const size_t len)
Funkce zkopiruje data z virtualni pameti volajiciho vlakna do
virtualni pameti vlakna @thr. Vraci EOK pokud byla data zkopirovana,
EINVAL pokud je identifikace zdrojoveho vlakna neplatna.
Integrace s testy
-----------------
K integraci s testy vytvorite hlavickovy soubor assignment-2.h, ktery bude
obsahovat deklarace vsech vyse uvedenych funkci. Typicky bude obsahovat
#include direktivy, ktere zajisti vlozeni vasich hlavickovych souboru
s prislusnymi deklaracemi.
Rozsirene zadani -----------------------------------------------------------
Sprava oblasti virtualni pameti
-------------------------------
Sprava oblasti virtualni pameti zahrnuje alokaci, manipulaci a
uvolnovani oblasti virtualni pameti v kontextu virtualniho adresoveho
prostoru prave beziciho vlakna. Oblasti se nesmi prekryvat, velikost a
zacatek oblasti musi byt zarovnan na nejmensi velikost stranky
podporovanou procesorem, v pripade MIPS R4000 tedy 4 KiB.
Pozadavky na rozhrani pro spravu virtualni pameti zachovava zakladni
chovani pozadovane pro zakladni zadani, pocet oblasti virtualni
pameti jiz vsak nesmi byt omezen zadnou predem definovanou konstatnou.
Pro spravu oblasti virtualni pameti pouzijte vhodnou datovou strukturu
(nikoliv staticky alokovanou), pricemz duraz je kladen na rozumne rychle
nalezeni oblasti virtualni pameti k dane virtualni adrese.
* int vma_alloc(
void **from, const size_t size, const unsigned int flags)
Funkce alokuje oblast ve virtualnim adresovem prostoru o velikosti
@size bajtu, pro tuto oblast alokuje fyzickou pamet a vytvori mapovani
prave alokovane virtualni pameti do fyzicke.
V zavislosti na hodnote bitoveho priznaku VF_VIRT_ADDR v argumentu
@flags funkce bud automaticky zvoli vhodnou adresu zacatku oblasti
virtualni pameti a vrati ji ve @from (hodnota VF_VA_AUTO), nebo se
pokusi vytvorit oblast na adrese zadane volajicim ve @from (hodnota
VF_VA_USER).
Bitove pole VF_ADDR_TYPE v argumentu @flags urcuje typ segmentu
virtualniho adresoveho procesoru, ve kterem bude virtualni oblast
alokovana. Hodnoty bitoveho pole pro jednotlive segmenty jsou
VF_AT_KUSEG, VF_AT_KSEG0, VF_AT_KSEG1, VF_AT_KSSEG a VF_AT_KSEG3.
Alokace v segmentech KSEG0 a KSEG1 se vzajemne vylucuji, pokud jsou
mapovany na stejne fyzicke adresy.
Binarni format argumentu @flags je dan makry VF_VA_SIZE, VF_VA_SHIFT
a VF_AT_SIZE, VF_AT_SHIFT, ktere specifikuji velikost bitoveho pole
a jeho pozici ve slove.
Vraci EOK pokud byla pamet alokovana a namapovana, EINVAL pokud
nebylo mozne alokovat oblast se zacatkem na adrese @from v danem
segmentu virtualniho adresoveho prostoru procesoru, nebo pokud
@from ci @size nejsou zarovnany, ENOMEM pokud neni dostatek fyzicke
pameti k provedeni operace.
* int vma_free(void *from)
Funkce zrusi mapovani pameti pro oblast se zacatkem na adrese @from,
ktera byla predtim vytvorena volanim vma_alloc(). Dale uvolni fyzickou
pamet, do ktere byla oblast mapovana a zrusi prislusnou oblast
virtualni pameti.
Vraci EOK pokud byla pamet uvolnena a mapovani zruseno, EINVAL pokud
@from neukazuje na zacatek oblasti vytvorene volanim vma_alloc().
* int vma_resize(void *from, const size_t size)
Funkce zvetsi/zmensi velikost oblasti virtualni pameti, jejiz zacatek
lezi na adrese @from, na novou velikost @size bajtu. Nesmi pritom
dojit k prekryvu dvou ruznych oblasti virtualni pameti.
Vraci EOK, pokud byla velikost oblasti uspesne zmenena, EINVAL
pokud @from neukazuje na platnou oblast, pokud by melo dojit
k prekryvu s jinou oblasti v dusledku zvetseni, nebo pokud neni nova
velikost zarovnana, ENOMEM pokud nebylo mozne oblast zvetsit v kvuli
nedostatku pameti.
* int vma_remap(void *from, void *to)
Funkce premapuje oblast zacinajici na adrese @from na adresu @to.
Velikost oblasti a posloupnost mapovani virtualnich stranek na fyzicke
zustava zachovana. Prekryti virtualnich adres v oblasti @from a @to
je pripustne.
Vraci EOK pokud bylo premapovani uspesne, EINVAL pokud na adrese
@from neni platna oblast, pokud @to neni zarovnana adresa, nebo pokud
by pri presunu melo dojit k prekryti jiz existujici oblasti.
* int vma_merge(void *area1, void *area2)
Funkce spoji oblasti @area1 a @area2 do jedne oblasti, pokud spolu
sousedi. Zacatek nove oblasti je na nizsi z pocatecnich adres obou
oblasti. Vraci EOK pokud bylo spojeni provedeno, EINVAL pokud jsou
jedna nebo obe oblasti neplatne, nebo pokud spolu nesousedi.
* int vma_split(void *from, void *split)
Funkce rozdeli oblast zacinajici na adrese @from na dve sousedici
oblasti, pricemz nove vznikla oblast bude zacinat na adrese @split.
Vraci EOK pokud bylo rozdeleni uspesne, EINVAL pokud @from neukazuje
na zacatek existujici oblasti, pokud @split neni uvnitr rozdelovane
oblasti, nebo pokud hodnota @split neni zarovnana.
Novy alokator pameti
--------------------
Implementujte novy alokator kernelove pameti jako funkcni nahradu
jednoducheho alokatoru z 1. semestralni prace. Alokator bude vracet
pouze pamet ze segmentu KSEG0 virtualniho adresoveho prostoru procesoru,
tj. bude mozne k alokovane pameti pristupovat bez pouziti TLB.
Navrhnete privatni rozhrani alokatoru tak, aby bylo mozne snadno behem
behu volit mezi ruznymi alokacnimi strategiemi.
Implementujte v kodu nejmene tyto alokacni strategie:
* first fit
* next fit
* best fit
* worst fit
Navrhnete a implementujte take vhodny vicevlaknovy test, ktery bude
implementovane alokacni strategie testovat a merit dobu provadeni
jednotlivych operaci a pametovy overhead. V dokumentaci potom uvedte
porovnani jednotlivych strategii.
Verejne rozhrani alokatoru odpovida a rozsiruje rozhrani
z 1. semestralni prace:
* void *malloc(const size_t size)
Funkce alokuje blok pameti pozadovane velikosti z heapu. Vraci NULL
pokud nebylo mozne blok alokovat, jinak ukazatel na zacatek alokovaneho
bloku.
* void free(const void *ptr)
Funkce uvolni blok pameti, na ktery ukazuje ptr.
* int malloc_strategy(unsigned int strategy)
Funkce prepne prave pouzivanou alokacni strategii. Pozadovane
strategie budou oznaceny makry STRATEGY_FIRST_FIT, STRATEGY_NEXT_FIT,
STRATEGY_BEST_FIT a STRATEGY_WORST_FIT. Po uspesnem prepnuti strategie
bude navratova hodnota EOK, pro neznamou strategii bude EINVAL.
More information about the NSWI004
mailing list