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. Pokud jste zvolili 1. semestralni praci v rozsirene variante, je nutne, aby take 2. semestralni prace pracovala korektne v konfiguraci s vice procesory. 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. * int frame_alloc(void **paddr, const size_t cnt, const unsigned int flags) Funkce nalezne a alokuje @cnt po sobe jdoucich volnych fyzickych stranek pameti. V pripade, ze je @cnt je rovno nule nebo alokace nebyla uspesna, vraci ENOMEM. V opacnem pripade vraci EOK. V zavislosti na hodnote bitoveho priznaku VF_VIRT_ADDR v argumentu @flags funkce bud automaticky zvoli vhodnou fyzickou adresu zacatku alokovanych fyzickych stranek a vrati ji ve @paddr (hodnota VF_VA_AUTO), nebo se pokusi o alokaci zacinajici na fyzicke adrese zadane volajicim ve @paddr (hodnota VF_VA_USER). 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. 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. 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. * int frame_free(const void *paddr, const size_t 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, const 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(const 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(const 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(const 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 api.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(const 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(const 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(const void *from, const 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(const void *area1, const void *area2) Funkce spoji oblasti zacinajici na @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(const void *from, const 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. Implementujte nejmene tyto alokacni strategie: * first fit * next fit * best fit * worst fit Vyber pozadovane alokacni strategie bude mozny v dobe prekladu, napriklad pomoci nastaveni hodnoty vhodneho makra na konstanty STRATEGY_FIRST_FIT, STRATEGY_NEXT_FIT, STRATEGY_BEST_FIT a STRATEGY_WORST_FIT. Privatni rozhrani alokatoru by melo byt navrzeno tak, aby umoznovalo snadne rozsirovani o dalsi volitelne alokacni strategie. 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. -- Posledni modifikace: 2008/01/08 22:20