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 pevnym identickym mapovanim (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 -------------------------- V kontextu operacniho systemu je virtualni adresovy prostor, nebo take nazyvany 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 typicky alokovan po souvislych 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 je jednim z prostredku sdilenych vsemi vlakny jednoho 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 uzivatelskym 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 vm_flags_t 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 bitovych priznaku v argumentu @flags funkce bud automaticky zvoli vhodnou fyzickou adresu zacatku alokovanych fyzickych stranek a vrati ji ve @paddr (priznak VF_VA_AUTO), nebo se pokusi o alokaci zacinajici na fyzicke adrese zadane volajicim ve @paddr (priznak VF_VA_USER). Pokud je v argumentu @flags uveden bitovy priznak 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 adresoveho prostoru, tedy v rozsahu fyzickych adres [0x00000000,0x20000000). Naopak priznaky 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 samotneho alokatoru apod.) nebo fyzicke stranky drive alokovane volanim funkce frame_alloc() a dosud neuvolnene. * 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 samotneho 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 souvisly interval fyzickych stranek, ktery byl vsak postupne 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 nebyla drive alokovana pomoci frame_alloc(). Uprava stavajiciho alokatoru haldy ---------------------------------- Stavajici alokator kernelove haldy s rozhranim malloc()/free() alokuje pamet primo 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 jako svuj backend rozhrani frame_alloc()/frame_free() a zaroven aby vzdy 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 thread_flags_t 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. Zaroven je pripustne, aby operace nad temito datovymi strukturami mely linearni slozitost v zavislosti na hodnote konstanty MAX_AREAS, lze tedy napriklad pouzit staticke pole. * int vma_map( void **from, const size_t size, const vm_flags_t 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 bitovych priznacich v argumentu @flags funkce bud automaticky zvoli vhodnou adresu zacatku oblasti virtualni pameti a vrati ji ve @from (priznak VF_VA_AUTO), nebo se pokusi vytvorit oblast na adrese zadane volajicim ve @from (priznak VF_VA_USER). Dalsi bitove priznaky v argumentu @flags urcuji typ segmentu virtualniho adresoveho procesoru, ve kterem bude virtualni oblast alokovana. Hodnoty priznaku 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. Funkce 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_unmap(const void *from) Funkce zrusi mapovani pameti pro oblast se zacatkem na adrese @from, ktera byla predtim vytvorena volanim vma_map(). 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_map(). 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. Hlavickovy soubor api.h by mel take obsahovat makro FRAME_SIZE, jehoz hodnota bude odpovidat velikosti fyzicke stranky (ramce), resp. virtualni stranky v bajtech, kterou kernel pouziva. 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 (a tudiz i nalezeni odpovidajici fyzicke adresy), casova slozitost takove operace by tedy mela byt lepsi nez linearni vzhledem k poctu oblasti. Rozumnymi kandidaty na takovou datovou strukturu jsou naprikad vhodne stromove struktury, vhodne hashovaci struktury nebo hierarchicke strankovaci tabulky. Motivace a cile pro vyber pouzite datove struktury dukladne rozeberte v dokumentaci. * int vma_map( void **from, const size_t size, const vm_flags_t 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 bitovych priznacich v argumentu @flags funkce bud automaticky zvoli vhodnou adresu zacatku oblasti virtualni pameti a vrati ji ve @from (priznak VF_VA_AUTO), nebo se pokusi vytvorit oblast na adrese zadane volajicim ve @from (priznak VF_VA_USER). Dalsi bitove priznaky v argumentu @flags urcuji typ segmentu virtualniho adresoveho procesoru, ve kterem bude virtualni oblast alokovana. Hodnoty priznaku 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. Funkce 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_unmap(const void *from) Funkce zrusi mapovani pameti pro oblast se zacatkem na adrese @from, ktera byla predtim vytvorena volanim vma_map(). 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_map(). * 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 nebo zvetseni oblasti za hranici prislusneho segmentu. 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 haldy ------------------- Implementujte novy alokator kernelove haldy 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 a benchmark, ktery bude implementovane alokacni strategie testovat a merit dobu provadeni ruznych operaci, pametovy overhead a fragmentaci. V dokumentaci potom uvedte porovnani jednotlivych strategii. Verejne rozhrani alokatoru odpovida 1. semestralni praci: * 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: 2010/10/10 19:40