Куча

Аллокаторы

Куча структурно представляет собой много блоков памяти, которые или заняты, или свободны.

картинка

Самих реализаций аллокаторов много, все отличаются друг от друга структурой хранения блоков, стратегией и алгоритмом поиска блоков и самой организации блоков.

Если максимально обобщать, работа аллокаторов сводится к выполнению двух операций — выделения блока памяти malloc и освобождения блока памяти free.

Во время вызова malloc происходит примерно следующее:

Среди свободных блоков ищется блок подходящего размера.

Используются разные стратегии: может выбираться как первый подходящий (first-fit), как самый маленький среди подходящих (best-fit), так и самый большой среди подходящих (worst-fit).

Если блок найден не был, то куча расширяется и появляются новые свободные блоки.
Если найденный блок не совпадает по размеру с запрашиваемым, он делится на два. Например, если был запрошен блок в $20$ байт, а аллокатор нашёл блок в $32$ байта, аллокатор поделит найденный блок на два блока — один в $20$ байт и второй в $12$ байт.
Выбранный блок помечается занятым и передаётся программе.

Во время вызова free происходит примерно следующее:

Выбранный блок помечается свободным
Свободный блок объединяется с соседними свободными блоками в один большой свободный блок.

Классический first-fit

Этот алгоритм был первым алгоритмом раздачи памяти в C. Появился он ещё в 1970-х годах в самых первых версиях Unix и C, разработанных в Bell Labs. При этом держался такой алгоритм долго, даже в 1985 году Давид Корн на конференции USENIX говорит об этом алгоритме как о всё ещё распространённом.

Аллокатор был реализован как кольцевой односвязный список. В списке хранились блоки памяти с заголовком — указателем на следующий блок next. В те времена размер указателя был всего $2$ байта. Длина блока вычислялась неявно по формуле

\text{размер данных текущего блока} = \text{адрес следующего блока}~\code{next} - \text{адрес текущего блока} - \text{длина заголовка}

Блоки были выровнены по $2$ байтам, поэтому младший бит next был всегда $0$ . Его использовали как флаг занятости блока: $0$ — блок свободен, $1$ — блок занят.

Когда malloc находил адрес свободного блока, он сдвигал его на длину заголовка и возвращал сдвинутый адрес, пряча тем самым заголовок.

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

Объединение во время выполнения операции free не происходит. Там просто освобождаемый блок помечается свободным. Объединение будет произведено во время следующего обхода списка при выполнении операции malloc.

Накладные расходы на память у такого аллокатора минимальны. Но есть две проблемы: невысокая производительность и внешняя фрагментация. Быстро накапливаются мелкие свободные блоки, при этом при большом количестве свободной памяти какой-нибудь большой кусок выделить невозможно — просто нет такой непрерывной свободной области. Да и слияние блоков во время malloc неэффективно.

Алгоритм двойных меток

Алгоритм двойных меток был разработан Дональдом Кнутом в 1962 году при работе над Burroughs 5000.

Структура аллокатора такая же, как и у первого алгоритма first-fit. По краям блоков находятся метки, хранящие информацию об обоих смежных блоках, а именно их длины и занятость.

Системные вызовы

mmap (memory map) — системный вызов в Unix-подобных системах, который отображает файлы или устройства в память процесса. Его также используют для анонимного выделения памяти, без привязки к файлу.

void* mmap(void* addr, size_t length, int prot, int flags,
           int fd, off_t offset);

void* addr — желаемый адрес для размещения. Если NULL, то ядро выберет адрес само. Если не пусто, будет попытка разместить блок памяти по указанному адресу.

size_t length — размер выделяемой области памяти. Округляется вверх до кратного размеру страницы.

int prot — флаги защиты памяти (protection flags). Определяет права доступа к выделенной памяти, а точнее к странице памяти. Можно комбинировать через |.
PROT_READ — чтение, можно читать из памяти;
PROT_WRITE — запись, можно записывать в память;
PROT_EXEC — исполнение, можно исполнять как код;
PROT_NONE — нет доступа, память полностью недоступна.

int flags — тип и свойства памяти. Определяет поведение выделенной памяти, а точнее страниц памяти. Можно комбинировать через |.
MAP_SHARED — общее отображение, изменения видны другим процессам и записываются в файл;
MAP_PRIVATE — приватное отображение, изменения не видны другим, используется Copy-on-Write;
MAP_ANONYMOUS — анонимное отображение, не связанное с файлом, применяется для кучи;
MAP_FIXED — точное расположение, требуется разместить точно по addr, даже если придётся перекрыть какое-то существующее отображение;
MAP_FIXED_NOREPLACE — как и точное расположение, но перекрытие существующих отображений невозможно;
MAP_POPULATE — сразу выделить физические страницы;
MAP_LOCKED — заблокировать, страницы не могут быть вытеснены в swap;
MAP_HUGETLB — использовать большие страницы.

int fd — файловый дескриптор для отображения в память. Для анонимного отображения должно быть -1.

off_t offset — смещение в файле, с которого нужно начинать отображение. Для анонимного отображения должно быть 0.

void* ptr = mmap(NULL, size, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

if (ptr == MAP_FAILED) {
    perror("mmap failed");
    return 1;
}

printf("Выделено: %p\n\n", ptr);

strcpy((char*)ptr, "Hello from mmap!");
printf("Прочитали: %s\n\n", (char*)ptr);

for (size_t i = 0; i < size - 1; i++) {
    ((char*)ptr)[i] = 'A' + (i % 26);
}
((char*)ptr)[size - 1] = '\0';

Упражнения

Придумайте последовательность вызовов malloc и free, которая заставит классический алгоритм first-fit работать за время $O(n)$ на каждый вызов malloc. Объясните, как блуждающий указатель смягчает эту проблему, но не решает её полностью.

Напишите классический first-fit аллокатор. Подумайте над его оптимизацией. Можно разделить общий список блоков на несколько списков по размеру блоков: в одном списке будут только очень маленькие блоки, в другом побольше, и так далее.