poma12390/c-memory-allocator

Аллокатор памяти на C

Memory allocator

---

Аллокатор памяти

Мы уже неоднократно пользовались аллокатором памяти, который является частью стандартной библиотеки 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) его вызывать!

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

Дополнительные материалы

• Ulrich Drepper. "What every programmer should know about memory"

• man mmap online

• Статья Doug Lea о том, как работает аллокатор в glibc. Текущая версия аллокатора работает по более сложному алгоритму.

• Исходный код одной из последних версий аллокатора в glibc. Очень много хорошо написанных комментариев