Приветствую, уважаемый читатель!
В первой части мы реализовали простейший аллокатор с минимальным оверхедом. Конечно же на самом деле все сложнее. Так реализация дефрагментации была наивной и не могла сливать блоки даже когда не было распределенных блоков после нескольких вызовов mem_free. Для того, что бы получить исходную картинку где будет только 2 служебных блока и один свободный нужно было бы вызвать mem_alloc с размером большим чем доступно памяти что бы искусственно запустить дефрагментацию. В этой части мы это исправим и напишем юнит тест для нашего аллокатора что бы убедится что он работает правильно.
Слияние за константное время
Для реализации слияния за константное время и при чем в обе стороны нам нужно что бы список был двусвязным. Для этого добавим кое что в заголовок блока, а именно: размер предыдущего блока памяти:
Теперь у нас перед заголовком с размером блока и битом состояния находится размер предыдущего блока для того, что бы мы могли получить указатель на него при желании.
В стуктуру _MemoryBlock добавлены новые поля:
// Размер оверхеда static constexpr const int _S_total_overhead_size = _S_header_size + sizeof (size_t); // Размер предыдущего блока добавлен ПЕРЕД заголовком size_t* _M_prev_blk_size = nullptr; // Как и прежде uint8_t* _M_block = nullptr; // Конструктор как и некоторые функции члены изменился: _MemoryBlock(uint8_t* __addr) : _M_block(__addr) { if (_M_block) { _M_prev_blk_size = reinterpret_cast<size_t*>(_M_block - sizeof(size_t)); } }Как и следовало ожидать за все нужно платить. Теперь размер оверхеда 16 байт на 64 битной машине. Как и минимальный размер блока. Теперь он тоже 16 байт. Забегая вперед я скажу что это сделано для того, что бы блок любого допустимого размера при освобождении можно было приделать в двусвязный список свободных блоков, т. е. минимум 16 байт нужно для двух полей _M_prev и _M_next по 8 на каждую. Из сказанного следует теперь что размер зарезервированной области стал 64 байта, а не 32 как ранее. Теперь минимальный размер блока 16 байт и оверхед 16, что в сумме 32. Два специальных блока, а значит в сумме 64 байта.
Но теперь мы можем реализовать слияние за константное время! Для этого нам нужно реализовать кое какие методы и изменить уже имеющиеся:
// Функция установки размера предыдущего блока void __put_prev_blk_size(size_t __prev_blk_size) noexcept { *reinterpret_cast<size_t*>(__header() - _S_header_size) = __prev_blk_size; } // Расчитывает вдрес заголовка предыдущего блока _MemoryBlock __prev_implicit_block() const noexcept { return _MemoryBlock(__header() - *_M_prev_blk_size - _S_total_overhead_size); }Это позволяет реализовать слияние блоков в обе стороны!
// Пытается слить блоки и возвращает указатель // на получившийся блок или на тот же самый блок того же размера // если слияние не удалось _MemoryBlock __try_consolidate() noexcept { auto __res = *this; // сначала проверяем следующий auto __blk = __next_implicit_block(); _MemoryBlock __b = _MemoryBlock::__null_block(); // если он своболный, сливаемся с ним if (!__blk.__is_null() && __blk.__is_free()) { // как и раньше приделываем к себе в заголовок новый размер // не забываем размер оверхеда, раз блок сливается, то оверхеда // у него нет, так как он формально больше не существует как // независмый __put_to_header(__size() + __blk.__size_with_overhead()); // приделываем свой размер следующему блоку __b = __next_implicit_block(); if (!__b.__is_null()) { __b.__put_prev_blk_size(__size()); } } // теперь пробуем слиться с предыдущим __blk = __res.__prev_implicit_block(); if (!__blk.__is_null() && __blk.__is_free()) { // меняем его размер, с оверхедом!!! __blk.__put_to_header(__size() + __blk.__size_with_overhead()); // корректируем размер следующего блока __b = __blk.__next_implicit_block(); if (!__b.__is_null()) { __b.__put_prev_blk_size(__blk.__size()); } } // вуаля, теперь все прелестно! return __res; }Само собой __slice тоже изменилась:
_MemoryBlock __slice(size_t __sz) noexcept { if (__sz > 0) { __sz = __aligned_size(__sz); // нарезаем теперь только с начала кучи if (__sz < __size()) { size_t __new_sz = __size() - __sz; __put_to_header(__sz, _BlockState::_S_allocated); auto __n = __next_implicit_block(); __n.__put_to_header(__new_sz - _S_total_overhead_size, _BlockState::_S_free); // заполняем размер предыдущего блока обязательно! __n.__put_prev_blk_size(__size()); return *this; } else if (__sz == __size()) { // тут больше ничего делать не нужно __put_to_header(__sz, _BlockState::_S_allocated); return *this; } else { ALOGD( "%s(): current block size (%lu) less than requested (%lu). Ignore " "request", __func__, __size(), __sz); } } return __null_block(); }Теперь мы готовы победить фрагментацию одновременно и просто и эффективно, просто сливать каждый раз блоки когда они освобождаются. Таким образом у нас всегда константное наихудшее время требующее проверки и слияния блоков с каждой стороны.
Вот реализация:
void mem_free(void* __p) noexcept { // we should be able savely called with nullptr if (__p != nullptr) { auto __blk = _MemoryBlock_t::__from_user_space_memory(__p); if (!__blk.__is_null() && __blk.__is_allocated()) { __blk.__unallocate(); __blk.__try_consolidate(); } } else { ALOGE("Unknown block '%p'", __p); } }Проверим теперь как это работает. Вот код теста:
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); utils::alloc_malloc::__dump(); 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 0x564b1f2f2ec0 size 16 size with overhead 32 state allocated _MemoryBlock:block address 0x564b1f2f2ee0 size 4016 size with overhead 4032 state freeprev blk size 16 _MemoryBlock:service block address 0x564b1f2f3ea0 size 16 size with overhead 32 state allocated _MemoryBlock:**********************END OF MEMORY DUMP********************** _MemoryBlock:total memory 4048 bytes _MemoryBlock:total memory with overhead 4096 bytes _MemoryBlock:total allocated memory 32 bytes _MemoryBlock:total free memory 4016 bytes _MemoryBlock:total total_blocks count 3 _MemoryBlock:*************************MEMORY DUMP************************* _MemoryBlock:service block address 0x564b1f2f2ec0 size 16 size with overhead 32 state allocated _MemoryBlock:block address 0x564b1f2f2ee0 size 16 size with overhead 32 state allocatedprev blk size 16 _MemoryBlock:block address 0x564b1f2f2f00 size 16 size with overhead 32 state allocatedprev blk size 16 _MemoryBlock:block address 0x564b1f2f2f20 size 3952 size with overhead 3968 state freeprev blk size 16 _MemoryBlock:service block address 0x564b1f2f3ea0 size 16 size with overhead 32 state allocated _MemoryBlock:**********************END OF MEMORY DUMP********************** _MemoryBlock:total memory 4016 bytes _MemoryBlock:total memory with overhead 4096 bytes _MemoryBlock:total allocated memory 64 bytes _MemoryBlock:total free memory 3952 bytes _MemoryBlock:total total_blocks count 5 _MemoryBlock:Unknown block '(nil)' _MemoryBlock:*************************MEMORY DUMP************************* _MemoryBlock:service block address 0x564b1f2f2ec0 size 16 size with overhead 32 state allocated _MemoryBlock:block address 0x564b1f2f2ee0 size 4016 size with overhead 4032 state freeprev blk size 16 _MemoryBlock:service block address 0x564b1f2f3ea0 size 16 size with overhead 32 state allocated _MemoryBlock:**********************END OF MEMORY DUMP********************** _MemoryBlock:total memory 4048 bytes _MemoryBlock:total memory with overhead 4096 bytes _MemoryBlock:total allocated memory 32 bytes _MemoryBlock:total free memory 4016 bytes _MemoryBlock:total total_blocks count 3Как видно после освобождения всех блоков куча имеет исходный вид, словно ничего и не было. Снова только два служебных блока и один большой свободный.
Юнит тест
Собственно тестировать мы будем инварианты аллокатора о которых говорим уже вторую статью. Но как это сделать? На первый взгляд это кажется трудным, но! Это выполнимо. Для того что бы это было возможным аллокатор реализован именно так как это есть. Т.е. заголовочный файл со структурой которую можно будет включить в тест, это делает тестирование до безобразия простым. Дальше тест должен банально покрыть инварианты.
Тут я рассмотрю только отдельные тесты, кому нужны детали добро пожаловать в репозиторий
Проверяем слияние:
TEST(AllocatorTest, merge_test) { std::vector<char*> pointers; pointers.reserve(MEM_ALLOC_ARRAY_LEN); char* p = nullptr; _MemoryBlock_t block = _MemoryBlock_t::__from_user_space_memory(p); size_t expected_block_size = _MemoryBlock_t::_S_total_overhead_size; size_t prev_blk_size = _MemoryBlock_t::_S_total_overhead_size; // проверям корректность заголовка for (int i = 1; i < 8; i++) { p = memory_alloc(i); pointers[i] = p; block = _MemoryBlock_t::__from_user_space_memory(p); ASSERT_EQ(block.__is_allocated(), true); ASSERT_EQ(block.__is_free(), false); ASSERT_EQ(block.__size(), expected_block_size); // размер минимум с оверхед ASSERT_EQ(block.__size_with_overhead(), _MemoryBlock_t::_S_total_overhead_size + block.__size()); // размер предыдущего блока ASSERT_EQ(*block._M_prev_blk_size, prev_blk_size); } auto first = _MemoryBlock_t::__from_user_space_memory(pointers[1]); // при освобождении блоки сливаются for (int i = 1; i < 8; i++) { block = _MemoryBlock_t::__from_user_space_memory(pointers[i]); expected_block_size = block.__size(); auto __n = block.__next_implicit_block(); if (!__n.__is_null() && __n.__is_free()) { expected_block_size += __n.__size_with_overhead(); } memory_free(pointers[i]); ASSERT_EQ(block.__is_allocated(), false); ASSERT_EQ(block.__is_free(), true); // проверяем размер блока после слияния ASSERT_EQ(block.__size(), expected_block_size); ASSERT_EQ(block.__size_with_overhead(), _MemoryBlock_t::_S_total_overhead_size + block.__size()); // размер предыдущего блока должен быть корректным ASSERT_EQ(*block._M_prev_blk_size, prev_blk_size); if (i > 1) { prev_blk_size += block.__size_with_overhead(); } } // тоже самое для первого блока. Он должен быть теперь единственный свободный ASSERT_EQ(first.__is_allocated(), false); ASSERT_EQ(first.__is_free(), true); ASSERT_EQ(first.__size(), HEAP_SIZE - (_MemoryBlock_t::_S_total_overhead_size * 5)); ASSERT_EQ(first.__size_with_overhead(), HEAP_SIZE - (_MemoryBlock_t::_S_total_overhead_size * 4)); ASSERT_EQ(*first._M_prev_blk_size, _MemoryBlock_t::_S_total_overhead_size); } Тест для realloc:
TEST(AllocatorTest, mem_realloc_test) { char* p0 = memory_alloc(100); char* p1 = memory_alloc(200); char* p2 = memory_alloc(100); const char* str = "Hello world!"; // Теперь мы нарезаем блоки только с начала кучи // значит порядок такой: // p0, p1, p2 // порождаем ситуацию когда p1 может быть расширен за счет p2 // так как тот гарантировано свободен memory_free(p2); // копируем строку в p1 strcpy(p1, str); char* old_ptr = p1; // и увеличивем размер p1 p1 = memory_realloc(p1, 220); // p1 должен быть увеличен за счет p2, т.е. наращивание с конца // по сути просто удилнение. Т.е. буквально изменение размера в заголовке :-) // Следовательно указатель не должен измениться ASSERT_EQ(p1, old_ptr); // данные должны быть на месте ASSERT_STREQ(p1, str); old_ptr = p0; strcpy(p0, str); // теперь получается должен быть перераспределен блок // нарезаем от начала p0 = memory_realloc(p0, 300); // адреса разные ASSERT_NE(old_ptr, p0); // новый указатель распределен снова, значит адрес должен быть больше ASSERT_TRUE(p0 > old_ptr); // данные должны быть скопированы ASSERT_STREQ(p0, str); // тут блок должен быть обрезан, ничего не меняется кроме его размера в // заголовке old_ptr = p0 p0 = memory_realloc(p0, 100); ASSERT_EQ(old_ptr, p0); ASSERT_STREQ(p0, str); memory_free(p0); memory_free(p1); }Вроде бы все. В следующей части обещали подвезти список свободных блоков, надеюсь доживем до бинов 😀
ссылка на оригинал статьи https://habr.com/ru/articles/861930/
Добавить комментарий