A4. Власний аллокатор

середнійспирається на модуль 10, модуль 12

Мета

Модуль 10 стверджує, що «найкраща відповідна» на практиці програє «першій відповідній». Переказати це твердження легко, а от повірити в нього не дуже, тож ви перевірите його на власних числах.

Заразом стане зрозуміло, чому malloc(8 ГіБ) спрацьовує на машині з чотирма гігабайтами пам’яті (модуль 12).

Що має вийти

Бібліотека з чотирма функціями та програма-стенд:

void *my_malloc(size_t size);
void  my_free(void *ptr);
void *my_realloc(void *ptr, size_t size);
void  my_heap_stats(struct heap_stats *out);

my_heap_stats повертає щонайменше: скільки байтів запитано, скільки віддано системою, кількість вільних ділянок і розмір найбільшої. З цих чисел і рахується фрагментація.

Етапи

Пам’ять у системи.

Беріть її через mmap з MAP_ANONYMOUS, великими шматками (наприклад, по 1 МіБ), і нарізайте самі. sbrk теж підійде, але mmap ближчий до того, як працюють сучасні аллокатори.

Зверніть увагу: mmap віддає адреси миттєво незалежно від розміру. Фізичні сторінки з’являться при першому записі — перевірте це, порівнявши VmSize і VmRSS у /proc/self/status.
Список вільних ділянок і «перша відповідна».

Кожна ділянка має заголовок із розміром і позначкою зайнятості. my_free повертає ділянку в список.
Злиття сусідів.

Без нього фрагментація зростає нескінченно: звільнені сусідні ділянки лишаються окремими й жодна не підходить під більший запит.

Найпростіше реалізувати через межові теги — розмір дублюється в кінці ділянки, щоб можна було подивитися на сусіда зліва.
Друга стратегія: «найкраща відповідна».

Вибір стратегії — прапорець або змінна середовища. Код спільний, різниця в одній функції пошуку.
Вимірювання.

Стенд генерує послідовність запитів і звільнень із заданим розподілом розмірів і часів життя, після чого друкує статистику.

Три профілі обов’язкові: однакові розміри (фрагментації майже немає), два різко різні розміри (найгірший випадок), розмір із важким хвостом (схоже на реальні програми).
Висновок.

Таблиця «стратегія × профіль → фрагментація, час пошуку». Якщо «найкраща відповідна» у вас виграла — опишіть, на якому профілі й чому; це теж коректний результат, але його треба пояснити.

Автоперевірка

Перевірка лежить в архіві з файлами курсу, і команди нижче виконуються з розпакованого каталогу.

cd labs/a4-allocator
./check.sh ./my_alloc_test

Перевірка ганяє послідовності виділень і звільнень, після кожного кроку контролює цілісність (записані дані не зіпсовані, ділянки не перетинаються) і перевіряє, що злиття справді відбувається.

Часті помилки

Немає вирівнювання. Адреса, яку повертає malloc, мусить бути вирівняна під найсуворіший тип, тобто alignof(max_align_t), зазвичай 16 байтів. Інакше SSE-інструкції на такому вказівнику дадуть помилку.

Заголовок псується. Запис на один байт за межі ділянки затирає заголовок сусіда. Це рівно те, від чого захищають канарки (модуль 16), до речі, можете додати їх і собі.

free(NULL) падає. За стандартом це цілком дозволена операція, яка нічого не робить.

Злиття тільки вправо. Половина сусідств лишиться незлитою, і фрагментація ростиме вдвічі швидше, ніж мала б.

Порівняння без прогріву. Перший mmap тягне за собою сторінкові винятки, тож робіть кілька повторів.

Далі, якщо цікаво

Додати класи розмірів, як у slab-аллокаторі, і порівняти зі своїми двома стратегіями. Або підмінити системний malloc через LD_PRELOAD і запустити на ньому справжню програму.