Uživatelský paměťový alokátor pro OS NOVA

Na tomto cvičení si zkusíte implementovat alokátor dynamické paměti, který bude využívat systémové volání brk z minulého cvičení.

Pro toto cvičení budete potřebovat:

• hotovou minulou úlohu
• vědět co je alokátor dynamické paměti (memory allocator) a způsoby implementace
  • https://cw.fel.cvut.cz/wiki/_media/courses/b4b35osy/lekce07.pdf
  • http://arjunsreedharan.org/post/148675821737/write-a-simple-memory-allocator
• spojové seznamy
  • https://en.wikipedia.org/wiki/Linked_list
• rozumět programování v C/C++
• připustit existenci volání malloc a free
  • https://linux.die.net/man/3/malloc

Implementujte jednoduchý alokátor paměti pro uživatelský prostor OS NOVA. Váš alokátor bude nabízet implementovat funkce my_malloc a my_free s následujícími prototypy:

void *my_malloc(unsigned int size)
int my_free(void *address)

Pro získání 4 bodů budou od alokátoru budou očekávány následující vlastnosti:

• Alokátor bude možné používat po přilinkování k aplikaci usr/hello.c ze zdrojových kódů OS NOVA.
• my_malloc alokuje paměť velikosti size a vrací adresu začátku alokované paměti. Pokud paměť požadované velikosti nelze alokovat, my_malloc vrací 0.
• my_free uvolní paměť alokovanou funkcí my_malloc. Parametr address je hodnota dříve vrácená funkcí my_malloc. Pokud je paměť úspěšně uvolněna, funkce vrátí 0, v opačném případě je vrácen nenulový kód chyby, který si můžete nadefinovat jak chcete.
• Pokud je my_free zavolána na již uvolněnou paměť nebo na paměť, která nebyla alokována voláním my_malloc, je to považováno za chybu. Můžete předpokládat, že program používající váš alokátor nemodifikuje jinou paměť na heapu než tu, vrácenou funkcí my_malloc.
• Bude schopná alokovat a uvolnit paměť.
• Bude používat systémové volání brk pro získání paměti pro alokaci.
• Pokud bude uživatel alokovat paměť po 16B. blocích (a větších), bude mít k dispozici alespoň 50% paměti, kterou je možné získat pomocí volání brk.
• Dealokovaná paměť půjde alokovat znovu.
• Paměť alokovaná funkcí my_malloc bude přístupná minimálně do doby zavolání my_free.
• Žádná část paměti alokované funkcí my_malloc nebude alokovaná znovu dříve než bude zavoláno odpovídající my_free.

Pro získání 8 bodů budou navíc vyžadovány následující vlastnosti:

• Po uvolnění menších sousedních bloků bude možné ve stejné oblasti alokovat jeden velký souvislý blok.

Co se odevzdává:
Archiv obsahující vaši implementaci v souboru user/mem_alloc.cc a soubor kern/src/ec_syscall z minulého cvičení. Můžete ho vytvořit pomocí následující řádky z kořenového adresaře NOVY (nebo si můžete upravit pravidlo hw11 v Makefilu):

zip hw11.zip kern/src/ec_syscall.cc user/mem_alloc.cc