В прошлой части я закончил обещанием, что настоящие аллокаторы получат каждый свою часть. Вот первый: аллокатор кучи (heap allocator). Он управляет большой областью от 0x90000000 вверх (около 1,5 ГБ).
Зачем она вообще нужна? Менеджер памяти из прошлой части мыслит целыми страницами по 4 КБ. А ядру (kernel) нужна память различного размера под структуры данных: 17 байт под имя, 200 байт под структуру, 1 килобайт под буфер. Целая страница 4 КБ на каждую мелочь была бы расточительством. Аллокатор нарезает из грубых страниц кусочки произвольного размера и делает это с помощью функций kmalloc и kfree.
Что возвращает kmalloc:
У каждой аллокации прямо перед ней распологается структура, MemoryBlock в 32 байта:
typedef struct MemoryBlock {
size_t size; // полезный размер
struct MemoryBlock* next; // следующий блок в списке свободных (NULL если занят)
bool free; // тот самый бит: свободен или занят
bool region_head; // здесь начинается целый регион страниц?
pid_t owner_tid; // кому принадлежит блок (для Reaper)
size_t region_size; // полный размер региона
} MemoryBlock; // лежит прямо ПЕРЕД данными пользователя
То есть в памяти всегда [ header, 32 b ][ твои данные, size b ]. То, что kmalloc тебе отдаёт, это указатель за header, саму её ты не видишь. А kfree просто считает ptr - 32 из твоего указателя, чтобы снова найти header с MemoryBlock.
Насчёт вопроса "где битмап" (карта памяти, битовая карта): его нет. Некоторые аллокаторы держат отдельную таблицу, по биту на единицу (1 байт, 32 байта, 64 байта), свободно или занято. Я делаю иначе. Единственный бит, это флаг free в голове каждого блока, а "картой" кучи служит сама цепочка блоков: каждый знает свой размер и где лежит следующий свободный. Для кусков произвольного размера это подходит лучше, чем bitmap фиксированных единиц. К слову сказать, что существует множество различных аллокаторов.
Список свободных блоков
Свободные блоки висят в одном списке, отсортированном по адресу:
static MemoryBlock* free_list = NULL; // все свободные блоки, по адресу
Занятый блок просто не находится в этом списке (free == false). То, что список отсортирован по адресу, имеет причину, которая становится понятна при освобождении блока памяти: так соседи в памяти стоят рядом и в списке.
kmalloc: first-fit, затем split
kmalloc работает по простейшему рабочему принципу, first-fit: берёт первый свободный блок, который подходит по размеру.
void* kmalloc(size_t size) {
if (size == 0) return NULL;
mutex_get(&heap_mutex, true);
// first-fit: найти первый свободный блок с достаточным местом
MemoryBlock** curp = &free_list;
while (*curp && (*curp)->size < size)
curp = &(*curp)->next;
if (*curp) { // нашли
MemoryBlock* blk = *curp;
*curp = blk->next; // снять со списка свободных
void* ret = allocate_from_block(blk, size); // при нужде разрезать
mutex_release(&heap_mutex);
return ret;
}
// иначе: взять свежие страницы через alloc_virt_pages ...
}
Чаще всего найденный блок больше нужного. Тогда его разрезают (split): передняя часть занимается, а из остатка делается новый свободный блок, который уходит обратно в список.
// блок достаточно велик, чтобы делить?
if (block->size >= size + MEMORY_BLOCK_SIZE + 1) {
MemoryBlock* tail = (MemoryBlock*)((char*)block + MEMORY_BLOCK_SIZE + size);
tail->size = block->size - size - MEMORY_BLOCK_SIZE;
tail->free = true;
insert_block_address_ordered(tail, &unused); // остаток обратно в список
block->size = size;
}
block->free = false;
block->owner_tid = current_tid();
return (char*)block + MEMORY_BLOCK_SIZE; // указатель ЗА header
Если подходящего свободного блока не нашлось вовсе, kmalloc запрашивает страницы у менеджера памяти (alloc_virt_pages), так называемый регион. Переднюю часть занимает, остаток идёт в список свободных. В header первого блока он отмечает region_head = true, что здесь начинается целый регион страниц, и это важно при освобождении (kfree).
Весь танец с "бубнами" на картинке
kfree: выставить флаг free, затем coalesce
Освобождение блоков памяти делает обратное действие:
void kfree(void* ptr) {
if (!ptr) return;
mutex_get(&heap_mutex, true);
MemoryBlock* block = (MemoryBlock*)((char*)ptr - MEMORY_BLOCK_SIZE); // найти голову
if (block->free) { /* двойное освобождение! ЗАПРЕТИТЬ */
return; }
block->free = true;
MemoryBlock* prev = NULL;
insert_block_address_ordered(block, &prev); // вставить по адресу
block = coalesce_neighbors(prev, block); // слить с соседями
// ... если освободился целый регион: вернуть страницы ...
}
Внутри происходят действия и каждое важнее, чем выглядит.
Проверка двойного освобождения. У занятого блока всегда free == false. Если тут уже true, кто-то освобождает тот же блок второй раз. Вместо того чтобы испортить список, я останавливаю действие (и логирую). Звучит педантично, но именно этот случай был одной из самых упрямых моих ошибок: блок, попавший в список свободных дважды и затем перекрывшийся с поздней аллокацией, а падение всплывало где-то совсем в другом месте, будто случайно.
Слияние (coalesce). Если освобождённый блок стоит прямо рядом с другим свободным, эти два объединяются в один большой:
// слить с последующим, если он лежит сразу за ним:
char* block_end = (char*)block + MEMORY_BLOCK_SIZE + block->size;
if (block_end == (char*)block->next) {
block->size += MEMORY_BLOCK_SIZE + block->next->size;
block->next = block->next->next;
}
Без этого куча (heap) со временем рассыпалась бы на бесчисленные крошечные обрывки, и в какой-то момент запрос на большой размер блока уже не смог бы быть выполнен, несмотря на большое количество свободной памяти в сумме. Поскольку список отсортирован по адресу, соседи стоят рядом и в списке, так что слияние дёшево.
Возврат страниц. Когда целый регион (та самая метка region_head) снова освобождается полностью, kfree возвращает его страницы через free_virt_pages менеджеру памяти. Так замыкается круг к прошлой части: что аллокатору кучи (heap allocator) больше не нужно, утекает обратно в общий котёл.
Учёт владельца: чтобы ничего не оставалось
Каждый занятый блок памяти помнит в owner_tid, какой поток (thread) его взял. Когда поток заканчивает свою работу, Thread Reaper освобождает все блоки с этим ID (heap_cleanup_thread), чтобы упавшая (или просто закончившая работу) программа не держала память вечно. Есть одно исключение: структуры, которые подсистема убирает сама при завершении процесса, помечаются через kheap_set_kernel_owned, иначе вышло бы двойное освобождение, когда Thread Reaper и подсистема захотят освободить один и тот же блок.
Остальные функции аллокатора кучи
Поверх kmalloc и kfree строятся дополнительные функции которые упрощают работу с выделением и освобождением блоков памяти:
- krealloc меняет размер уже выделенного блока(если ещё влезает в блок, он остаётся; иначе запрашивается новый и данные копируются туда),
- kcalloc это kmalloc плюс обнуление,
- aligned_kmalloc / aligned_kfree дают выровненную память, например по границам в 64 байта под буферы DMA,
- clear_kmemory обнуляет область,
- get_thread_heap_usage говорит, сколько поток (thread) сейчас использует памяти.
Все работают потокобезопасно (thread safe) через один и тот же heap_mutex.
Правда жизни
First-fit со слиянием прост и надёжен, но не самое быстрое решение, что можно построить. При большом количестве запросов и освобождений куча всё равно фрагментируется, список свободных блоков памяти становится длинным, а искать в длинном списке линейно "дорого". Для маленького ядра это вполне годится. Более шустрый аллокатор, который раскладывает свободные блоки по размеру в ящики (chunk box) (и для множества мелких одинаковых объектов, может, всё же использует битмап), у меня в голове есть, но ещё не построен :-) . Как часто бывает: сначала пусть работает правильно, быстро придёт позже.
◀ Предыдущая статья Содержание Следующая статья ▶
*Система не стоит на месте, поэтому в дальнейшем тексты могут не совпадать с реальным положением.