Аллокатор. Часть I.

23.06.2014

Есть немало задач в программировании, когда разработчику приходится писать собственный аллокатор. Вот вам навскидку такая прикладная задача. Пусть у нас есть приложение, которое работает в качестве сервера. Приложение принимает из сети объемные изображения, чтобы в ответ вернуть список распознанных на изображении объектов. Примем, что в процессе работы алгоритма нам приходится часто аллоцировать и освобождать небольшие участки памяти — до 100 кБ. Выделяем память мы при помощи функции malloc, а освобождаем при помощи функции free.

В стандартной библиотеке GNU libc используется мьютекс, который захватывается как в функции malloc, так и в функции free. Мьютекс необходим, чтобы избежать Data Race при работе с внутренними структурами аллокатора одновременно из нескольких потоков. Очевидно, что частое аллоцирование и освобождение малых участков памяти может заметно снизить скорость работы приложения. Если алгоритм будет выполняться на многопроцессорной машине, частое обращение к функциям malloc и free из разных потоков будет ощутимо сказываться на быстродействии. Одним из способов уменьшить накладные расходы может быть создание отдельного аллокатора для каждого потока, со своим диапазоном доступных адресов, который не будет использовать механизм межпоточной синхронизации.

В данной статье мы попытаемся реализовать такой аллокатор, простой, но вполне пригодный для использования, работающий на заранее заданном диапазоне адресов. Наш аллокатор не будет использовать механизмы межпоточной синхронизации в функциях аллоцирования и освобождения памяти, т.е. будет приспособлен для случая, когда в каждом потоке используется собственный инстанс аллокатора. Статья будет состоять из 3 частей. В первой части будут освещены различные подходы к реализации внутренней структуры аллокатора, а также дан краткий обзор некоторых широко используемых аллокаторов.

1. Постановка задачи

Любой разработчик, хоть раз сталкивавшийся с арифметикой указателей, сможет реализовать простой алгоритм аллоцирования памяти. Действительно, имея некий зарезервированный диапазон адресов, несложно написать функцию alloc(size), которая будет хранить информацию об уже аллоцированной области памяти. Например, такой алгоритм:

#define HEAP_SIZE 1024
static char buffer[HEAP_SIZE];

void* alloc(size_t sz)
{
    static size_t off = 0;
    char* ptr = 0;
    if(off + sz < HEAP_SIZE)
    {
        ptr = off;
        off += sz;
    }

    return ptr;
}

Такой аллокатор может быть применим для определенных задач, но алгоритм работает только в одном направлении, т.е. однажды аллоцировав память мы уже не можем ее освободить. А значит очень скоро мы исчерпаем весь доступный нам объем HEAP_SIZE. Очевидно, что в аллокаторах, предоставляемых стандартными библиотеками C и C++ используется другой подход.

Давайте попробуем разобраться как работает функция malloc. Когда мы вызываем данную функцию, она, в свою очередь, обращается к операционной системе. Операционная система, поскребя по сусекам, отдает нашему приложению одну или несколько страниц памяти. В результате работы фукнция malloc должна вернуть некий адрес, по которому расположен участок памяти запрошенного размера. Пусть наше приложение запросило 10 байт. Страница памяти на x86 имеет размер 4096 байт. Что же происходит с оставшимися 4 килобайтами? Логично предположить, что аллокатор припрятал оставшийся объем памяти. При повторном вызове malloc, функция уже не будет обращаться к ОС, а просто обратится к своему внутреннему хранилищу и достанет оттуда еще один участок памяти размером 10 байт. Соответственно, при вызове функции free аллокатор поместит освобождаемый участок памяти во внутренне хранилище.

Собственно, структура для хранения и учета свободной памяти, а также алгоритмы malloc и free, которые измененяют состояние внутреннего хранилища, и являются сердцем аллокатора. Каждый байт в диапазоне адресов, зарезервированном за аллокатором, может находиться в двух состояниях: аллоцирован (INUSE) или свободен (FREE). Однако, хранить состояние для каждого байта накладно. Поэтому вводят понятие блока памяти. Блок может быть фиксированного или переменного размера. Для учета блоков фиксированного размера существует два основных подхода: на основе битового массива и на основе связного списка.

Если ввести дополнительную структуру данных, битовый массив, и поставить в соответствие каждому блоку памяти определенный бит в массиве, который будет хранить состояние блока (1 — аллоцирован; 0 — свободен), тогда мы получим аллокатор на основе битового массива. Минус такого подхода в том, что он требует дополнительную память под битовый массив, размер которой пропорционален количеству блоков.

Гораздо практичнее устроен аллокатор на основе связного списка. Каждый блок содержит заголовок. В заголовке хранится размер блока в байтах и флаг CINUSE_BIT, описывающий состояние блока: аллоцирован или свободен. Каждый блок представлен дескриптором в связном списке элементов. При аллоцировании алгоритм проходит по списку и изменяет значение CINUSE_BIT одного или нескольких блоков. Несомненным плюсом данного подхода является то, что мы можем организовать связный список блоков, не используя дополнительную память.

Оба описанных подхода сочетают преимущества и недостатки, присущие всем аллокаторам, созданным на основе блоков фиксированного размера. С одной стороны, время поиска участка памяти, размер которого не превышает размер блока, будет минимальным — O(1). С другой стороны, время поиска участка свободных блоков необходимого размера (если размер запрошенного участка памяти больше размера блока) пропорционально как размеру доступной для аллокатора памяти, так и размеру запрошенного участка памяти — O(mn).

Решить эту проблему можно, если блоки памяти будут иметь переменный размер. В этом случае, если нам необходимо аллоцировать область памяти меньшего размера, чем размер свободного блока, мы просто делим текущий блок на два и аллоцируем один из них. Для того, чтобы поделить блок, необходимо изменить его заголовок (размер), и создать заголовок для нового свободного блока. Время поиска свободного блока подходящего размера в худшем случае будет линейным — O(n).

В используемом в GNU libc аллокаторе используется подход на основе блоков переменного размера, дополненный отдельными списками для блоков размером 16, 24, 32, 48, ..., 4096 байт. Таким образом, при аллоцировании участка памяти до 4 кБ, время поиска подходящего свободного блока будет O(1). Если же мы хотим аллоцировать больше 4 кБ, тогда время поиска будет O(n) в худшем случае.

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

2. Краткий экскурс в историю аллокаторов

Аллокатор на основе блоков переменного размера использовался Керниганом и Ричи в их варианте стандартной библиотеки для нового языка программирования С. Код аллокатора умещался в 200 строк и оперировал над односвязным замкнутым списком свободных блоков памяти, но при необходимости обращался к операционной системе для расширения диапазона доступных адресов. Код этого аллокатора приведен в их книге «The C Programming Language» [1] и настоятельно рекомендован для ознакомления всем начинающим программистам.

Аллокатор Кернигана и Ричи был написан в те незапамятные времена, когда память делилась на сегменты, и механизм своппинга сбрасывал на диск весь сегмент данных, в случае, если приложение находилось в неактивном состоянии. Но время шло, на смену сегментам пришла страничная организация памяти, а с ней и возможность использовать механизм своппинга для отдельных страниц памяти, а не для целых сегментов. В те времена все активно использовавшиеся аллокаторы строились на основе одно- или двусвязного списка свободных блоков памяти перемнного размера. Проблема заключалась в том, что обращение к заголовку свободного блока зачастую инициировало подгрузку страниц памяти с диска, даже если этот блок потом не использовался. Это пагубно сказывалось на производительности программ. Один из методов оптимизации предложил Пол Хеннинг Камп [2]. Его вариант аллокатора, более известный как pkmalloc опирался на идею хранения данных о страницах памяти аналогично тому как аллокатор хранит данные о блоках памяти. Для этого он предложил ввести своеобразный каталог страниц, и использовать его для учета свободных страниц памяти (таких страниц, внутри которых нет аллоцированных блоков памяти). Идея себя оправдала и аллокатор появился в составе стандартной библиотеки языка С в новой версии ОС FreeBSD 2.2.

Параллельно с Полом, свою версию аллокатора предложил Даг Ли. В его версии аллокатора (dlmalloc) вводились классы блоков, с фиксированными размерами от 16 до 4096 байт. Каждый класс был представлен двусвязным списком блоков соответствующего размера. Для аллоцирования участков размером более 4096 байт использовался подход на основе блоков переменного размера, как у Кернигана и Ричи. При поиске блока необходимого размера алгоритм не просматривал все блоки в списке, вынуждая операционную систему подгружать соответствующие страницы памяти с диска, а выбирал блок из соответствующего класса. Обращение к списку свободных блоков происходило только в случае, если объем запрошенной памяти превышал размер страницы.

Время шло, на смену однозадачным вычислительным машинам пришли быстрые многопроцессорные системы с большими объемами доступной оперативной памяти. Джейсон Эванс предложил версию аллокатора [3], известную как jemalloc, в котором особое внимание уделялось сокращению временных затрат на взаимную блокировку и учету NUMA в алгоритме (аллоцирование тех адресов памяти, время доступа к которым для данного процессора минимально). Сам Джейсон утверждает, что ему удалось добиться значительного сокращения времени работы алгоритма на многопроцессорных системах, не увеличив притом время работы функций malloc/free на системах с одним процессором.

В то же время в Google предложили свою версию аллокатора, оптимизированного для работы в многопоточном окружении: tcmalloc. В аллокаторе от Google вспомогательные структуры данных аллокатора хранятся в Thread Cache — локальном хранилище потока. Благодаря такому подходу им удалось реализовать lockless алгоритмы для аллоцирования и освобождения памяти. Исходный код tcmalloc доступен в [4].

3. Освобождение памяти

Способ хранения и учета свободных блоков памяти является сердцем аллокатора. Но не менее важен правильный и оптимальный алгоритм освобождения памяти. Давайте рассмотрим такой пример:

void* ptr_a = malloc(8); // Allocate 8 bytes: returns 0x0C01000 
void* ptr_b = malloc(8); // Allocate another 8 bytes: returns 0x0C01008 
free(ptr_a); // Release a 
free(ptr_b); // Release b 

void* ptr_c = malloc(16) ; // What will this allocation return?

В данном примере у аллокатора дважды запрашивается 8 байт. Затем эта память освобождается. Если алгоритм просто изменяет состояние блока при вызове функции free (сбрасывает флаг CINUSE_BIT), тогда после освобождения ptr_a и ptr_b по адресу 0x0C01000 располагались бы два свободных блока по 8 байт каждый. В сумме 16 байт. Однако при аллоцировании 16 байт для ptr_c ни один из этих блоков не соответствовал бы запрашиваемому размеру.

Почему так происходит — понятно. Но что с этим делать? Лучшим решением было бы обединить два подряд идущих свободных блока в один. Для этого мы можем добавить еще один флаг (PINUSE_BIT), который хранит состояние блока, располагающегося «левее» текущего. Если этот флаг сброшен, значит «левее» освобождаемого блока находится еще один пустой блок. Это сигнал, что эти два подряд идущих блока можно объединить. Аналогично, можно проверить блок, расположенный непосредственно после текущего. Если флаг CINUSE_BIT в заголовке этого блока сброшен, значит мы также можем их объединить. В результате из двух или трех близко расположенных блоков должен получиться один б'ольшего размера. Одно из следствий такого подхода: между любыми двумя свободными блоками должен располагаться хотя бы один аллоцированный.

На практике, для оптимизации времени поиска свободного блока блоки не объединяют, если они меньше какого-то определенного размера. Например, в алгоритме, предложенном Дагом Ли, если освобождался блок размером 64 байта, то он не объединялся с соседями, а добавлялся в список для соответствующего класса блоков.

В следующей части статьи будет представлено описание нашего будущего аллокатора: структуры данных, алгоритмы аллоцирования и освобождения памяти, вспомогательные функции. А на сегодня все. Arrivederci!

Автор: Алексей Комнин

Список литературы:

  1. B. Kernighan and D. Ritchie, The C Programming Language. Prentice Hall, Inc., 2nd ed., 1988
  2. P.-H. Kamp, «Malloc(3) revisited»
  3. J. Evans, «A Scalable Concurrent malloc(3) Implementation for freebsd», 2006
  4. P. M. Sanjay Ghemawat, «Tcmalloc: Thread-caching malloc»

Последние записи блога

Напишите нам

Хотите разработать приложение? Требуется логотип или сайт?

Мы открыты для сотрудничества! Вы можете отправить нам сообщение прямо сейчас.

+7

Обновить