Доброго времени суток.
При разработке ОС на с++ мы сталкиваемся с рядом трудностей, таких как отсутствие стандартной библиотеки и ABI с++ и прочее в этом духе. При чем перед реализацией PageAllocator и прочих аппаратных механизмов хотелось бы иметь какую то стандартную библиотеку позволяющую делать хоть что то. Об этом и пойдет речь.
Далее я расскажу о своем опыте разработки таких алгоритмов для своей ОС и о том, как их тестировать у себя на своей рабочей системе с юнит тестами и прочим, прикручивая в итоговую демку проверенный тестами код, и начну я с аллокатора.
Речь пойдет о немного переделанном алгоритме Кнута неявный список блоков с граничными тегами который описан в конце третьего тома в разделе "Распределение памяти". Его идея предельно проста:
Мы берем некоторый отрезок памяти, назовем его кучей и разбиваем его на блоки такого вида:
Где block_size размер блока, а далее за ним следует бит состояния который говорит нам о том распределен блок (allocated) или нет (free), размер и бит состояния находятся в одном машинном слове. См. ниже. Padding можем игнорировать, у нас он будет входить в часть блока которую можно использовать, т.е. будет включен в payload
Как видно на картинке у нас есть 2 специальных заголовка: один в начале блока, а другой в конце. Это упрощает реализацию слияния при освобождении блока и позволяет выполнить его за константное время. Но создает дополнительный оверхед в виде двух тегов вместо одного, т.е. список двусвязный.
Мы же реализуем немного более сложную схему, но за то с вдвое меньшим оверхедом, т.е. односвязный список (forward_list) у нас блок будет иметь следующий вид:
Значение полей заголовка тоже самое, но тег только один. В заголовке. Зеленое пространство блока это то, что можно использовать клиентам аллокатора. При такой схеме слияние (coleascing) немного усложняется и замедляется. Но при этом размер служебного оверхеда будет не 16 байт на 64 битной машине, а 8. Так как у нас хранится не два тега, а только один. На 64 битной системе размер size_t 8 байт, на 32 битной 4. Соответственно на 32 битной машине оверхед при наличии дух тегов был бы 8, а станет 4.
Получается распределяя память мы заполняем заголовок и возвращаем указатель на первый байт после него, т.е. зеленого пространства.
Вкратце пробежимся по стилю и приступим к реализации. Стиль разработки STL так называемый uglification: для функций членов и локальных переменных используем префикс __ например __size(), для членов данных _M_, например _M_block, статические переменные имеют префис _S_, например _S_variable.
Обозначим некоторые свойства аллокатора:
1) Размер любого блок памяти должен быть выровнен по размеру адреса, это позволит нам упаковать ссостояние блока в размер так как биты 0-3 (для x86_64) размера всегда будут нулевыми.
Для работы с заголовком у нас есть следующие функции:
// Как упоминалось выше размер и бит состояния хранятся вместе в одном поле
void __put_to_header(size_t __size, _BlockState __state = _BlockState::_S_free) noexcept
{
*reinterpret_cast<size_t*>(__header()) = __size | static_cast<int>(__state);
}
inline bool __is_allocated() const noexcept
{
return (*reinterpret_cast<size_t*>(__header()) & 0x01) ==
static_cast<int>(_BlockState::_S_allocated);
}
bool __is_free() const noexcept
{
return !__is_allocated();
}
inline uint8_t* __header() const noexcept
{
return _M_block;
}2) Если запрошен размер блока меньше, мы выставляем его в минимальный размер, т.е. размер адреса и так же нужно учитывать еще и оверхед в виде заголовка, т.е. минимальный размер фактически использованной памяти получается 16 байт даже если пользователь попробует выделить всего 1.
Для простоты мы будем исходить из того, что память уже есть, например мы могли бы загрузиться грубом и отвести в загрузчике некоторый сегмент для кучи ядра, сейчас же для простоты будем выделять память стандарнтым аллокатором или из стека.
Вот список функций который мы реализуем:
// Инициализация кучи
int mem_init(uint8_t *__start, size_t __size_in_bytes) noexcept;
// Аналог malloc
void* mem_malloc(size_t __size) noexcept;
// Аналог calloc, т.е. выделяет память под массив и инициализирует ее нулями
void* mem_calloc(size_t __num, size_t __size) noexcept;
// Аналог realloc т.е. перераспределяет память и переносит содержимое блока
// в другой при необходимости
void* mem_realloc(void *__p, size_t __new_sz) noexcept;
// Аналог free
void mem_free(void* __p) noexcepНам потребуются указатели на начало и конец нашей кучи:
static uint8_t* _S_heap_start = nullptr;
static uint8_t* _S_heap_end = nullptr;И вспомогательная структура _MemoryBlock:
// Ее реализация будет ниже
template <std::size_t _PointerSize> struct _MemoryBlock;
using _MemoryBlock_t = detail::_MemoryBlock<__SIZEOF_POINTER__>;Функция mem_init инициализирует указатели на начало и конец кучи принимая аргументы __start - начало кучи и __size_in_bytes - размер в байтах. Для простоты реализации указатель имеет тип uint8_t для упрощения арифметики указателей что бы все рабоало безпреобразований типов.
Так же мы создадим два служебных блока минимального размера, т.е. __SIZEOF_POINTER__ + столько же заголовок. Служебные блоки будут расположены первый в начале и второй в конце, а между ними будет свободное для распределения пространство. Это упростит нам слияние.
Т.е. это как раз и будут _S_heap_start и _S_heap_end
int mem_init(uint8_t *__start, size_t __size_in_bytes) noexcept
{
if (__start != nullptr && __size_in_bytes > 0)
{
// Размер заголовка _S_header_size совпадает с размером указателя
// Размеры резервных службных блоков, их 2, т.е. _S_header_size * 2
size_t __reserved_block_size = _MemoryBlock_t::_S_header_size << 1;
// Минимальный размер блока совпадает с размером заголовка, так что все умножаем на
// колчество служебных блоков, т.е. на 2
// В переменной __total_reserver_space будет находится полный размер служебных
// блоков вместе с оверхедом
size_t __total_reserved_space = __reserved_block_size << 1;
// Инициализируем указатели на начало и конец таким образом что бы они оба указывали
// на заголовок блока
detail::_S_heap_start = __start;
detail::_S_heap_end = detail::_S_heap_start + __size_in_bytes - __reserved_block_size;
// Инициализируем заголовок первого служебного блока
_MemoryBlock_t __heap_start(detail::_S_heap_start);
__heap_start.__put_to_header(_MemoryBlock_t::_S_header_size, _MemoryBlock_t::_BlockState::_S_allocated);
// Инициализируем заголовок первого и пока что единственного свободного блока
// Если мы правильно инициализировали заголовок, что функция _MemoryBlock::__next_implicit_block
// вернет нам адрес на заголовок следующего неявного блока
_MemoryBlock_t heap = __heap_start.__next_implicit_block();
// Принимаем в расчет размер оверхеда самого блока
// total heap size - reserved space - heap memory block overhead size
// получается что размер свободного блока это размер кучи минус
// размеры служебных блоков с оверхедом минус оверхед самого блока
heap.__put_to_header(__size_in_bytes - __total_reserved_space - _MemoryBlock_t::_S_header_size,
_MemoryBlock_t::_BlockState::_S_free);
// Инициализируем заголовок второго служебного блока
_MemoryBlock_t __heap_end = heap.__next_implicit_block();
__heap_end.__put_to_header(_MemoryBlock_t::_S_header_size, _MemoryBlock_t::_BlockState::_S_allocated);
return 0;
}
return EINVAL;
}После вызова этой функции наш аллокатор готов к использованию.
Функция _MemoryBlock::__next_implicit_block() имеет следующий вид:
// Все тривиально, заголовок + размер + размер заголовка получается указатель
// на заголовок следующего блока
_MemoryBlock __next_implicit_block() const noexcept
{
return _MemoryBlock(__header() + __size() + _S_header_size);
}Все довольно просто: мы получаем указатель на заголовок и прибавляем к нему размер самого заголовка и размер блока. Тут все просто.
Теперь функция выделения памяти, наш аналог malloc:
void* mem_malloc(size_t __size) noexcept
{
if (__size > 0)
{
// Ищем первый подходящий блок выравненного размера!
auto block = __mem_find_fist_fit(_MemoryBlock_t::__aligned_size(__size));
if (block.__is_null())
{
// Если не нашли пытаемся слить свободные блоки
__try_merge_free_blocks();
// И ищем первый подходящий свободный блок снова
block = __mem_find_fist_fit(__size);
}
if (!block.__is_null())
{
// Если наши, отрезаем от него нужный кусок и возвращаем указатель на
// его клиентскую часть, т.е. начало блока + размер заголовка
// получается следующий байт сразу за заголовком
return block.__slice(__size).__user_space_memory();
}
ALOGE("Out of memory");
}
return nullptr;
}Функция __mem_find_fist_fit ищет первый попавшийся блок размером большим и равным нужному:
_MemoryBlock_t __mem_find_fist_fit(size_t __size)
{
if (detail::_S_heap_start != nullptr && detail::_S_heap_end != nullptr)
{
for (_MemoryBlock_t __cur_blk = detail::_S_heap_start; __cur_blk.__header() <= detail::_S_heap_end;
__cur_blk = __cur_blk.__next_implicit_block())
{
if (__cur_blk.__is_free() && __cur_blk.__size() >= __size)
{
return __cur_blk;
}
}
}
return _MemoryBlock_t::__null_block();
}Прежде чем идти дальше рассмотрим более детально функции которые находятся под капотом, а именно:
// Эта функция делит текущий блок на 2 откусывая кусок памяти с конца
// разумеется если блок больше чем __sz
_MemoryBlock __slice(size_t __sz) noexcept
{
if (__sz > 0)
{
__sz = __aligned_size(__sz);
if (__sz < __size())
{
size_t __new_sz = __size() - (__sz + _S_header_size);
// Меняем размер блока в заголовке на новый
__put_to_header(__new_sz, _BlockState::_S_free);
// и таким образом вынуждаем __next_implicit_block() вернуть нам
// указатель на место где должен распалагаться заголовок нового блока
// и заполяем его.
// Вот все, здравствуй мир, мы готовы!
__next_implicit_block().__put_to_header(__sz, _BlockState::_S_allocated);
return __next_implicit_block();
}
else if (__sz == __size())
{
// Если блок именно такого размера как нужно, просто выставляем бит состояния
// в allocated
__put_to_header(__sz, _BlockState::_S_allocated);
return *this;
}
else
{
// Ругаемся и отдаем невалидный блок
ALOGD(
"%s(): current block size (%lu) less than requested (%lu). Ignore "
"requestn",
__func__, __size(), __sz);
}
}
return __null_block();
}
// Слияние тоже простое
// В оригинальном алгоритме мы могли бы сделать это в mem_free так как теги были
// в начале и в конце блоков, в нашей реализации мы будем пробовать проходить список
// когда нужно вправо т.к. он у нас односвязный :-)
bool __try_coalesc_with_next_implicit_block() noexcept
{
if (__is_free())
{
auto __next = __next_implicit_block();
// если мы свободны и следующий блок тоже
if (!__next.__is_null() && __next.__is_free())
{
// то просто меняем свой размер в заголовке на сумму своего размера и
// и размера следующего блока
__put_to_header(__size() + __next.__size() + _S_header_size);
__next = __next_implicit_block();
// делаем тоже самое пока у нас получается. Это дает эффект слияния всех
// последовательно идущих свободных блоков подряд
while (__next.__try_coalesc_with_next_implicit_block())
{
__put_to_header(__size() + __next.__size() + _S_header_size);
__next = __next_implicit_block();
}
return true;
}
}
return false;
}Имея эти функции попытка слияния возможных свободных блоков становится тривиальным делом. Простой цикл. Я думаю тут нечего комменировать :-) Мы просто пробегаем весь список и пробуем слить текущий блок со следующим.
static void __try_merge_free_blocks()
{
ALOGD("trying to merge blocks ...");
if (detail::_S_heap_start != nullptr && detail::_S_heap_end != nullptr)
{
for (_MemoryBlock_t __cur_blk = _MemoryBlock_t::__from_user_space_memory(detail::_S_heap_start);
__cur_blk.__header() < detail::_S_heap_end;
__cur_blk = __cur_blk.__next_implicit_block())
{
__cur_blk.__try_coalesc_with_next_implicit_block();
}
}
}Освободжение памяти тоже тривиально:
void mem_free(void* __p) noexcept
{
// Не ломаемся если нам передали нулевой указатель
if (__p != nullptr)
{
// Получаем блок из указателя на заголовок
auto block = _MemoryBlock_t::__from_user_space_memory(__p);
// В теории каким то образом может получится так, что вместо заголовка
// мы получим nullptr в случае освобождения како го нибудь кривого указателя
// на массив
if (!block.__is_null()) {
// если блок не распределен не ломаемся
if (!block.__is_null() && block.__is_allocated()) {
block.__unallocate();
block.__try_coalesc_with_next_implicit_block();
}
}
return;
}
// Но ругаемся на этой
ALOGE("Unknown block '%p'", __p);
}calloc тоже несложный:
void* mem_calloc(size_t __num, size_t __size) noexcept
{
size_t __sz = __size * __num;
void *p = mem_malloc(__sz);
if (p != nullptr)
{
__sz = _MemoryBlock_t::__aligned_size(__sz);
memset(p, 0, __sz);
}
return p;
}Мы просто меняем бит состояния в заголовке и пробуем слиться со следующими свободными блоками.
Далее остается только реализация функции mem_realloc, тут придется немного подумать:
void* mem_realloc(void *__p, size_t __new_sz) noexcept
{
if (__p == nullptr)
{
ALOGD("Block '%p' is null. Allocating memory with size(%lu)...", __p, __new_sz);
// Если указатель нулевой обрабатываем это как выделение памяти размера
// __new_sz cppreference гласит что так нужно делать
// https://en.cppreference.com/w/c/memory/realloc
return mem_malloc(__new_sz);
}
_MemoryBlock_t __blk = _MemoryBlock_t::__from_user_space_memory(__p);
if (__blk.__is_allocated())
{
if (__new_sz > 0)
{
if (__blk.__size() == __new_sz)
{
ALOGD("new block size exactly as needed!");
// Если __p и так такого размера ничего не делаем, просто возвращаем тот же указатель
return __p;
}
if (__new_sz > __blk.__size())
{
// Если __p маленький, пробуем слиться со следующим блоком
ALOGD("new size is above than current. Trying to coleasc");
__blk.__try_coalesc_with_next_implicit_block();
}
if (__blk.__size() > __new_sz)
{
// Если __p больше, откусываем от него кусок и отдаем. Копирование тоже не нужно
ALOGD("new block size more than needed, slicing ...");
return __blk.__slice(__new_sz).__user_space_memory();
}
// Если выше ничего не вышло, то придется выделить новый блок памяти, перенести
// в него содержимое __p, освободить
void* __new_blk = mem_malloc(__new_sz);
if (__new_blk != nullptr)
{
ALOGD("Trying to allocate new block and copy contents of old one there");
memcpy(__new_blk, __blk.__user_space_memory(), __blk.__size());
__blk.__unallocate();
__blk.__try_coalesc_with_next_implicit_block();
return __new_blk;
}
ALOGD("No memory for new block. mem_realloc failed!");
}
}
else
{
// if block is not allocated do nothing, just return nullptr. actually it's UB
ALOGE("Block '%p' is not allocated!", __p);
}
return nullptr;
}Попробуем теперь использовать наш аллокатор
#include <iostream>
#include <memory>
#include <vector>
#include "allocator.h"
using namespace std;
#define HEAP_SIZE 4096LU * 4
#define COUNT 20
#define PTR_SIZE 30
uint8_t* memory_alloc(size_t size) {
return reinterpret_cast<uint8_t*> (utils::alloc_malloc::mem_malloc(size));
}
int main()
{
std::unique_ptr<uint8_t[]> heap(new uint8_t[HEAP_SIZE]);
utils::alloc_malloc::mem_init(heap.get(), HEAP_SIZE);
std::vector<uint8_t*> pointers;
pointers.reserve(COUNT);
for (int i = 0; i < COUNT; i++) {
pointers[i] = memory_alloc(i);
}
utils::alloc_malloc::__dump();
for (int i = 0; i < COUNT; i++) {
utils::alloc_malloc::mem_free(pointers[i]);
}
utils::alloc_malloc::__dump();
return 0;
}
Получаем такой вывод:
_MemoryBlock: *************************MEMORY DUMP*************************
_MemoryBlock: service block address 0x55c717d21eb8 size 8 size with overhead 16 state allocated
_MemoryBlock: block address 0x55c717d21ec8 size 15832 size with overhead 15840 state free
_MemoryBlock: block address 0x55c717d25ca8 size 32 size with overhead 40 state allocated
_MemoryBlock: block address 0x55c717d25cd0 size 32 size with overhead 40 state allocated
_MemoryBlock: block address 0x55c717d25cf8 size 32 size with overhead 40 state allocated
_MemoryBlock: block address 0x55c717d25d20 size 24 size with overhead 32 state allocated
_MemoryBlock: block address 0x55c717d25d40 size 24 size with overhead 32 state allocated
_MemoryBlock: block address 0x55c717d25d60 size 24 size with overhead 32 state allocated
_MemoryBlock: block address 0x55c717d25d80 size 24 size with overhead 32 state allocated
_MemoryBlock: block address 0x55c717d25da0 size 24 size with overhead 32 state allocated
_MemoryBlock: block address 0x55c717d25dc0 size 24 size with overhead 32 state allocated
_MemoryBlock: block address 0x55c717d25de0 size 24 size with overhead 32 state allocated
_MemoryBlock: block address 0x55c717d25e00 size 24 size with overhead 32 state allocated
_MemoryBlock: block address 0x55c717d25e20 size 16 size with overhead 24 state allocated
_MemoryBlock: block address 0x55c717d25e38 size 8 size with overhead 16 state allocated
_MemoryBlock: block address 0x55c717d25e48 size 8 size with overhead 16 state allocated
_MemoryBlock: block address 0x55c717d25e58 size 8 size with overhead 16 state allocated
_MemoryBlock: block address 0x55c717d25e68 size 8 size with overhead 16 state allocated
_MemoryBlock: block address 0x55c717d25e78 size 8 size with overhead 16 state allocated
_MemoryBlock: block address 0x55c717d25e88 size 8 size with overhead 16 state allocated
_MemoryBlock: block address 0x55c717d25e98 size 8 size with overhead 16 state allocated
_MemoryBlock: service block address 0x55c717d25ea8 size 8 size with overhead 16 state allocated
_MemoryBlock: **********************END OF MEMORY DUMP**********************
_MemoryBlock: total memory 16208 bytes
_MemoryBlock: total memory with overhead 16384 bytes
_MemoryBlock: total allocated memory 376 bytes
_MemoryBlock: total free memory 15832 bytes
_MemoryBlock: total total_blocks count 22
_MemoryBlock: Unknown block '(nil)'
_MemoryBlock: *************************MEMORY DUMP*************************
_MemoryBlock: service block address 0x55c717d21eb8 size 8 size with overhead 16 state allocated
_MemoryBlock: block address 0x55c717d21ec8 size 15832 size with overhead 15840 state free
_MemoryBlock: block address 0x55c717d25ca8 size 504 size with overhead 512 state free
_MemoryBlock: service block address 0x55c717d25ea8 size 8 size with overhead 16 state allocated
_MemoryBlock: **********************END OF MEMORY DUMP**********************
_MemoryBlock: total memory 16352 bytes
_MemoryBlock: total memory with overhead 16384 bytes
_MemoryBlock: total allocated memory 16 bytes
_MemoryBlock: total free memory 16336 bytes
_MemoryBlock: total total_blocks count 4Код доступен в репозитории. Благодарю за внимание!
В следующей статье будем разбираться как писать юнит тест к аллокатору.
Автор: GNU_Dimarik
