3. cvičenie – alokátor ?

Alokátor pre xv6

Pre toto cvičenie sme nahradili stránkový alokátor jadra xv6 buddy alokátorom. Na cvičení použijete tento alokátor na alokáciu a uvoľnovanie súborových štruktúr, aby xv6 mohol používať viac ako NFILE súborových deskriptorov. Alokátor budete taktiež optimalizovať na redukciu využitej pamäte. Cvičenie ste úspešne dokončili, ak váš alokátor prejde testami alloctest a usertests.

Na úvod sa prepnite do vetvy alloc:

Na tomto cvičení pracujte len so súbormi kernel/buddy.c a kernel/file.c.

Problém

xv6 má implementovaný iba stránkový alokátor a nemôže dynamicky alokovať objekty menšie ako jedna stránka. Menšie objekty sú potom deklarované staticky – napríklad pole štruktúr file, pole štruktúr proc atď. Týmto vzniká obmedzenie počtu súborov, ktoré môžu byť v systéme otvorené (s ktorým ste sa možno stretli v prvom cvičení). Ich počet je určený veľkosťou staticky alokovaného poľa súborov, ktoré má NFILE položiek (viď. kernel/file.c a kernel/param.h).

Riešenie

Riešením tohoto problému je použiť buddy alokátor z druhej prednášky a tretieho seminára, ktorý nájdete v zdrojákoch xv6 kernel/buddy.c a kernel/list.c.

Užitočné vysvetlenie teórie aj implementácie buddy alokátora nájdete na blogu BitSquid.

Úloha

Vašou úlohou je vylepšiť alokáciu pamäte xv6 dvoma spôsobmi:

  • Upravte kernel/file.c tak, aby počet súborových štruktúr bol obmedzený voľným miestom v pamäti a nie konštantou NFILE. Použite buddy alokátor.
  • Buddy alokátor nevyužíva miesto v pamäti efektívne. Pole alloc obsahuje bit pre každý buddy blok na každej úrovni. Na seminári sme ukázali chytrú optimizáciu, ktorá využije jeden bit na uchovanie stavu dvoch blokov. Hodnota tohoto bitu je B1_je_volny XOR B2_je_volny pre buddy pár blokov B1 a B2. Po každej alokácii alebo uvoľnení bloku musíte hodnotu tohoto bitu prehodiť. Napríklad, ak B1 a B2 sú alokované, bit bude nulový. Ak v tomto stave uvoľníme blok B1 alebo B2, bit nastavíme na 1. Ak je alokačný bit 1 a blok B2 je uvoľnený, tak vieme, že B1 a B2 môžu byť zlúčené. Ušetrením pol bitu na blok pre správu pamäte s veľkosťou 128 MB ušetríme 1 MB pamäte.

Program alloctest

Na otestovanie funkčnosti vašej implementácie by ste mali použiť program alloctest (viď. user/alloctest.c). Má dva testy:

Prvý test alokuje viac ako NFILE súborových štruktúr. Dosiahne to otvorením veľkého množstva procesov, kde každý otvorí veľa súborových deskriptorov. Tento test okamžite zlyhá na xv6 bez buddy alokátora.

Druhý test vytvorí proces, ktorý alokuje čo najviac pamäte a zlyhá vtedy, ak je veľkosť zvyšnej pamäte pod určitou hranicou. Ináč povedané, testuje koľko pamäte využíva kernel. Testom neprejde neoptimalizovaný buddy alokátor, ktorý máte pripravený v systéme.

Cvičenie môžete považovať za úspešné, ak váš kernel prejde testami alloctest aj usertests. Vo výstupe by to malo vyzerať takto:

Pomôcky

  • Na začiatok je určite dobré zmazať riadok 19 zo súboru kernel/file.c, ktorý deklaruje file[NFILE]. Namiesto neho alokujte struct file vo funkcii filealloc() použitím bd_malloc(). Nezabudnite alokovanú pamäť uvoľniť vo fileclose(), ff vtedy už nie je potrebná.
  • fileclose() musí získať zámok ftable.lock, ktorý chráni f->ref.
  • bd_malloc nijako neupravuje pamäť, ktorú vracia. Alokovaná pamäť obsahuje dáta, ktoré tam zostali z predchádzajúceho použitia. Používatelia tejto funkcie sa nemôžu spoliehať na to, že dostanú vynulovanú pamäť.
  • Použite funkciu bd_print() na vypísanie stavu alokátora.
  • Funkcia bd_init() je volaná s rozsahom fyzickej pamäte dostupnej na alokáciu. Z tejto pamäte potom bd_init() alokuje pamäť pre buddy dátové štruktúry. Svoje dátové štruktúry inicializuje nasledovne: bd_init označí pamäť buddy štruktúr ako alokovanú, aby si ju niekto neprivlastnil. bd_init() tiež zvláda prácu s pamäťou, ktorej veľkosť nie je mocninou dvojky tak, že označí nedostupnú pamäť ako alokovanú. K buddy alokátoru je tiež možné pristupovať z viacerých vlákien – konkuretné volania sú serializované zámkom.

    Týmto ste dokončili toto cvičenie. Zmeny môžete commitnúť do svojho repozitára.

    Voliteľný bonus

    Dynamicky alokujte inú dátovú štruktúru v xv6, ktorá je staticky alokovaná. Úprava niektorých štruktúr bude vyžadovať rozsiahlejšie úpravy (napríklad dynamická alokácia štruktúr proc), ale zvyšné sú jednoduché.