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

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

Мета

Модуль 10 стверджує, що «найкраща відповідна» на практиці не виграє в «першої відповідної» за щільністю, а програє їй у швидкості. Ви напишете власний malloc поверх mmap, реалізуєте обидві стратегії і перевірите це на трьох профілях запитів. Заразом ви побачите, що фізична пам’ять з’являється у процесі лише при першому записі, як описано в модулі 12.

Після цієї роботи ви зможете:

• написати аллокатор із заголовками ділянок, списком вільних і злиттям сусідів, який проходить перевірку цілісності й AddressSanitizer;
• пояснити, чому адреса з malloc кратна alignof(max_align_t) і що буде інакше;
• порахувати зовнішню і внутрішню фрагментацію з heap_stats і сказати, яка з них зростає на якому профілі;
• показати на VmSize і VmRSS, чому malloc(8 ГіБ) спрацьовує на машині з чотирма гігабайтами пам’яті;
• обґрунтувати числами вибір між «першою» і «найкращою відповідною».

Ті самі заголовки, списки вільних і злиття є всередині системного malloc, і розбір фрагментації у службі, яка працює тижнями, починається з них.

Завдання

Написати my_alloc.c за інтерфейсом із my_alloc.h і стенд, який ганяє аллокатор на трьох профілях запитів і друкує фрагментацію.

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);
void  my_set_fit(int best_fit);   // 0 — перша відповідна, 1 — найкраща

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

Що має вміти:

1. my_malloc повертає пам’ять, яку можна записати й прочитати назад; my_free(NULL) і my_malloc(0) не падають.
2. Адреси кратні alignof(max_align_t) для будь-якого розміру.
3. 64 блоки різного розміру не затирають одна одну.
4. my_realloc зберігає вміст і при зростанні, і при зменшенні.
5. Злиття сусідів: після звільнення всіх 64 блоків виділяється суцільна ділянка на половину вільної пам’яті, а вільних ділянок лишається не більше чотирьох.
6. Статистика узгоджена: requested ≤ obtained, free_bytes ≤ obtained, largest_free ≤ free_bytes.
7. 5000 випадкових виділень і звільнень до 1 КіБ не псують жодного блока.
8. Обидві стратегії розміщення з різницею лише у функції пошуку.

Обмеження. Лише C11. Пам’ять береться в системи через mmap або sbrk; malloc із libc всередині аллокатора не викликати. tests.c і my_alloc.h не змінюються: перевірка збирає їх зі свого каталогу.

Чого робити не треба. Потокобезпечність не потрібна: tests.c однопотоковий. Класи розмірів, як у slab-аллокаторі, і підміна системного malloc через LD_PRELOAD лишаються на «Далі, якщо цікаво».

Що записати у звіт:

• VmSize і VmRSS із /proc/self/status до і після першого запису у велику ділянку з mmap;
• таблицю «стратегія × профіль → зовнішня і внутрішня фрагментація, час пошуку» для профілів: однакові розміри, два різко різні, важкий хвіст;
• висновок, яка стратегія виграла на якому профілі; якщо виграла «найкраща відповідна», пояснення, чому.

Готово, коли:

• ./check.sh my_alloc.c: п’ятнадцять перевірок пройдено, AddressSanitizer мовчить;
• стенд друкує обидві фрагментації для кожної стратегії на кожному профілі;
• у звіті є таблиця і висновок.

Перед початком

• Прочитайте в модулі 10 розділи «Розподіл суцільними ділянками» і «Зовнішня фрагментація», а в модулі 12 розділи «Підкачка на вимогу» і «Як це насправді в Linux».
• Розпакуйте архів курсу: у labs/a4-allocator/ лежать my_alloc.h, tests.c і check.sh; скрипт збирає ваш my_alloc.c разом із tests.c.
• Знадобляться gcc з -fsanitize=address, man 2 mmap і man 5 proc (поля VmSize, VmRSS). Підійде будь-який Linux, зокрема контейнер і WSL2.

Етапи

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

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

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

2. Список вільних ділянок і «перша відповідна».

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

3. Злиття сусідів.

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

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

4. Друга стратегія: «найкраща відповідна».

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

5. Вимірювання.

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

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

6. Висновок.

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

Як рахувати фрагментацію

Зовнішня: 1 − найбільша_вільна_ділянка / загальна_вільна_памʼять. Одиниця означає, що вільна памʼять розсипана на дрібниці.

Внутрішня: (видано − запитано) / видано. Сюди входять заголовки й вирівнювання.

Друкуйте обидві окремо: вони поводяться протилежно, через що їх і плутають.

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

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

cd labs/a4-allocator
./check.sh my_alloc.c

Скрипт збирає ваш my_alloc.c разом із tests.c і ганяє п’ятнадцять перевірок: послідовності виділень і звільнень із контролем цілісності (записані дані не зіпсовані, ділянки не перетинаються), вирівнювання, realloc, злиття сусідів і статистику. Потім те саме повторюється під AddressSanitizer.

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

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

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

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

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

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

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

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