Assignment: Memory allocator
Лабораторная работа: аллокатор памяти
Подготовка
- Прочитайте про автоматические переменные в
Makefile
- Прочитайте главу 12 (стр. 235-239), главу 13 (целиком) "Low-level programming: C, assembly and program execution".
- Виртуальная память
- Освежите ваши знания о виртуальной памяти и её организации (глава 4 "Low-level programming: C, assembly and program execution").
- Вспомните, что такое файловые дескрипторы. С ними работают системные вызовы
open
,close
,write
и другие. - Прочитайте внимательно
map mmap
, в особенности значение флагаMAP_FIXED
иMAP_FIXED_NOREPLACE
.
- Возможности языка. Удостоверьтесь, что вы знаете о том, как работают:
- ключевые слова
inline
(стр. 280 в учебнике) иrestrict
(стр. 281 в учебнике). - Flexible array members (стр. 209 в учебнике).
- Макрос
offsetof
и особенно эта страница. - использование структур для создания новых псевдонимов типов (как просто
typedef
) но без неявного преобразования (см. урок на Stepik).
- ключевые слова
На защите мы можем обсуждать любые вопросы по этим материалам.
Аллокатор памяти
Мы уже неоднократно пользовались аллокатором памяти, который является частью стандартной библиотеки C.
Работа с ним осуществляется через функции malloc
и free
(а также calloc
и realloc
).
Чтобы лучше прочувствовать то, как он устроен, мы напишем свою упрощённую версию аллокатора.
Нулевое приближение
Аллокатор памяти позволяет запрашивать блоки произвольного размера, а затем ему можно эти блоки возвращать чтобы переиспользовать память.
Аллокатор резервирует большую область памяти с помощью mmap
. Он размечает её на блоки с заголовками, заголовки образуют связный список.
В заголовке указано, свободен ли блок, его размер и кто его следующий блок.
-
malloc(size_t n)
: ищем свободный блок размера не меньшеn
и делим его на два блока:- блок размера
n
- оставшаяся часть
При этом по ходу поиска мы объединяем соседние свободные блоки в свободные блоки большего размера.
- блок размера
-
При освобождении памяти мы помечаем блок как незанятый и объединяем со следующим блоком, пока возможно (пока и текущий и следующий блок свободны и пока следующий блок идёт в памяти сразу после данного).
-
Если большая область памяти кончается, мы резервируем ещё память. Сначала пытаемся сделать это вплотную, сразу после последнего блока, но если не получается — позволяем
mmap
выбрать подходящий адрес для начала нового региона.
Первое приближение
Представим себе достаточно большую область памяти, которую мы выделяем под кучу. Назовём её регионом. Разметим регион на блоки; каждый блок начинается с заголовка, а сразу после него идут данные.
|___заголовок1____|____данные1___||___заголовок2____|____данные2___||___заголовок3____|____...
Блоки заполняют собой всё пространство региона.
Заголовок
В заголовке блока содержится ссылка на следующий блок и пометка о статусе блока (занят или свободен).
/* mem_internals.h */
//См. https://stepik.org/lesson/408350/step/15
typedef struct { size_t bytes; } block_capacity;
struct block_header {
struct block_header* next;
block_capacity capacity;
bool is_free;
uint8_t contents[]; // flexible array member
};
Куча задаётся ссылкой на заголовок первого блока.
Размер и вместимость
У каждого блока есть две характеристики: размер и вместимость. Чтобы их не путать, мы создадим для них два типа.
/* mem_internals.h */
typedef struct { size_t bytes; } block_capacity;
typedef struct { size_t bytes; } block_size;
Размер блока всегда на offsetof(struct block_header, contents)
больше, чем его вместимость.
/* mem_internals.h */
inline block_size size_from_capacity( block_capacity cap ) {
return (block_size) {cap.bytes + offsetof( struct block_header, contents ) };
}
inline block_capacity capacity_from_size( block_size sz ) {
return (block_capacity) {sz.bytes - offsetof( struct block_header, contents ) };
}
- В заголовке хранится вместимость блока, а не его суммарный размер вместе с заголовком.
- Нельзя использовать
sizeof( struct block_header )
, т.к. из-за выравнивания размер структуры будет больше. На машине автора, например, размер структуры был равен 24, аoffsetof( struct block_header, contents ) == 17
, что правильно.
malloc(n)
Алгоритм - Перебираем блоки пока не находим "хороший".
Хороший блок — такой, в который можно уместить
n
байт. - Если хорошего блока не нашлось, то см. второе приближение.
- Хороший блок может быть слишком большим, скажем, нам нужно выделить 20 байт, а его размер 30 мегабайт. Тогда мы разделяем блок на две части: в первом блоке будет
20 + offsetof( struct block_header, contents )
байт. Адрес содержимого этого блока и вернётmalloc
.
free(void* addr)
Алгоритм - Если
addr == NULL
, то не делаем ничего. - Нам нужно получить из
addr
(который указывает на начало поляcontents
) адрес начала заголовка (для этого вычтем из негоsizeof(struct mem)
). В заголовке блока установимis_free = true
, всё.
Второе приближение
Теперь мы опишем ещё несколько аспектов аллокации.
- что делать с большим количеством последовательно идущих свободных блоков?
- как избежать появления слишком маленьких блоков?
- что делать, если память в куче кончилась?
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
, но только если он будет более красив и выразителен.
Для самопроверки
- Прочитайте правила хорошего стиля. Ваше решение должно им соответствовать.
- Проверьте архитектуру.
- Пожалуйста, присылайте решение в виде pull-request. Инструкция. В крайнем случае допускается ссылка на репозиторий на https://gitlab.se.ifmo.ru или https://github.com .
Дополнительные материалы
-
Ulrich Drepper. "What every programmer should know about memory"
-
Статья Doug Lea о том, как работает аллокатор в
glibc
. Текущая версия аллокатора работает по более сложному алгоритму.