Assignment: Memory allocator

---

Аллокатор памяти

• что делать с большим количеством последовательно идущих свободных блоков?
• как избежать появления слишком маленьких блоков?
• что делать, если память в куче кончилась?

Алгоритм malloc(n)

• Нет смысла выделять блок размером, скажем, 1 байт; даже его заголовок будет занимать больше места. Пусть минимальная вместимость блока будет обозначаться так:

    #define BLOCK_MIN_CAPACITY 24

  Слишком маленькие блоки могут образовываться в двух случаях:

  • n < BLOCK_MIN_CAPACITY. Тогда мы будем запрашивать блок не размера n, а размера BLOCK_MIN_CAPACITY.
  • Мы нашли хороший блок, и его размер немногим больше n. Если разделить блок на две части, вместимость второй части окажется меньше BLOCK_MIN_CAPACITY. Не будем делить такие блоки, а отдадим блок целиком.

• При поиске хорошего блока мы проходимся по блокам кучи. Прежде чем решать, хороший блок или нет, объединим его со всеми идущими за ним свободными блоками.

• Если в куче память кончилась, надо расширить кучу. Для этого будем использовать системный вызов mmap. Обязательно прочитайте man чтобы понять, с какими аргументами (prot и flags) его вызывать!

  • Сначала надо попытаться выделить память вплотную к концу кучи и разметить её в один большой свободный блок. Если в первом регионе кучи последний блок был свободен, надо объединить его со следующим.
  • Если выделить регион вплотную не получилось, то нужно выделить регион "где получится". Последний блок предыдущего региона будет связан с первым блоком нового региона.

Алгоритм free(void* addr)

• Помимо уже написанного про free, при освобождении блока можно объединить его со всеми следующими за ним свободными блоками.

Задание

• Реализуйте аллокатор
• Придумайте тесты, показывающие работу аллокатора в важных случаях:
  • Обычное успешное выделение памяти.
  • Освобождение одного блока из нескольких выделенных.
  • Освобождение двух блоков из нескольких выделенных.
  • Память закончилась, новый регион памяти расширяет старый.
  • Память закончилась, старый регион памяти не расширить из-за другого выделенного диапазона адресов, новый регион выделяется в другом месте. Тесты должны запускаться из main.c, но могут быть описаны в отдельном (отдельных) файлах. Алгоритм не самый простой, легко ошибиться. Чтобы не тратить времени на отладку, обязательно делайте разбиение на маленькие функции!
• Разберитесь с тем, как написан Makefile и исправьте его так, чтобы в итоговый код включался скомпилированный main.c. При желании вы можете написать свой Makefile, но только если он будет более красив и выразителен.