Приветствую читатель!
Для тех кто со мной впервые вот оглавление:
Код лежит тут
Подразумевается что читатель знаком с архитектурой аллокатора из части 3 и понимает алгоритм неявного списка свободных блоков который был освещен в части 1
Аллокатор работает стабильно, все тесты зеленые, включая тесты на стабильность. И следующим шагом логично бы реализовать перегрузки new и delete для abi, но вот незадача: там есть версии принимающие дополнительный аргумент, а именно выравнивание. Эту фичу я реализовать как раз забыл. В архитектуре которая рассматривается в предыдущей статье это оказалось простой, но интересной задачей. Ее мы и обсудим ниже.
Решение потребовало реализации функции mem_malloc_aligned которая выделит бОльший кусок памяти с учетом запрошенного выравнивания что бы мы там точно нашли правильно выровненный адрес.
Но что если адрес указателя из mem_malloc_aligned не совпадает с адресом указателя который вернул mem_malloc? Что делать в mem_free? Что делать в mem_realloc? Как мне работать с указателем перед которым не хедера?
Для начала я решил применить технику добавления смещения перед payload выровненного блока вместо хедера, смещения до payload изначального блока у которого есть хедер и футер.
Но как мне отличить offset от header? Я решил добавить magic number в хедер и футер увеличив тем самым размер оверхеда в 2 раза и раз уж от него считалось внутреннее выравнивание блоков памяти в аллокаторе и минимальный размер блока, то теперь минимальный размер блока стал 32 байта, а с оверхедом все 64. Теперь можно просто проверять magic number и если он не совпадает, то интерпретировать число на месте хедера как смещение до payload блока который вернул mem_malloc и далее получив на него указатель работать с блоком стандартным образом.
Самым простым способом добавить magic number было сделать его частью хедера и футера записывая его сразу же после байта с размером и состоянием в футере и перед ним в хедере.
Вот код:
static void mem_block_put_to_header(void *_p, size_t _sz, size_t state){ auto header = mem_block_header(_p); mem_block_pack(header, _sz, state); *mem_block_size_t_ptr(header + kMagicNumberSize) = kMagicNumber;}static void mem_block_put_to_footer(void *_p, size_t _sz, size_t state){ auto footer = mem_block_footer(_p); mem_block_pack(footer, _sz, state); *mem_block_size_t_ptr(footer - kMagicNumberSize) = kMagicNumber;}
Теперь внутреннее устройство аллокатора выглядит как на диаграмме ниже. Диаграмма отображает на диаграмме хедер, футер и мейджик как разные вещи, но это лишь для наглядности. По сути как говорилось выше теперь с точки зрения арифметики указателей аллокатора мейджик это часть хедера и футера.
Рассмотрим реализацию mem_malloc_aligned. Она просто считает новый размер блока так что бы там точно оказался указатель выровненный по нужной границе и размер пейлоада был верным, далее она просто вызывает mem_malloc, там накладываются требования на внутреннее выравнивание и получается еще бОльший кусок памяти, часть которого неизбежно будет неиспользованной …
Вот код:
// считаем размер памяти с выравниванием что бы мы 100% нашли там// адрес выровненный как надоstatic size_t mem_aligned_mem_size(size_t size, size_t align){ return size // в теории на ARM размер size_t и его выравнивание могу быть разными + max(sizeof(size_t), alignof(size_t)) + align - 1;}// возвращает адрес памяти выровненный по границе alignmentvoid *mem_malloc_aligned(size_t size, size_t alignment){ if (alignment >= kAlignment) { size_t size_with_alignment = mem_aligned_mem_size(size, alignment);// выделяем память обычным mem_malloc void *ptr = mem_malloc(size_with_alignment); if (ptr) {// считаем выровненный адрес той же формулой что и обычно считали размер для блока// только теперь учитываем sizeof(size_t) для offset auto address = reinterpret_cast<size_t>(ptr); auto aligned_ptr = reinterpret_cast<void *>(alignment * ((address + sizeof(size_t) /* offset */ + alignment - 1) / alignment)); if (aligned_ptr) {// считаем смещение до блока с которым можем работать, т.е. до памяти которую// выделил mem_malloc и записываем его как хедер выровненного блока mem_block_size_t_ptr(aligned_ptr)[-1] = mem_block_char_ptr(aligned_ptr) - mem_block_char_ptr(ptr); return aligned_ptr; } mem_free(ptr); } } return nullptr;}
Вот и вся магия!
Вот так выглядит блок который отдает mem_malloc_aligned:
Как видно на диаграмме часть блока не используется из за требований к выравниванию адресов, так же как видно у нас есть offset вместо хедера и мейджик после хедера и перед футером. Таким образом мы можем реализовать резолвинг блока как проверку мейджика и если он кривой, то блок либо сломан, либо был выделен mem_malloc_aligned
Кот код проверки:
static void *mem_block_resolve_from_align(void *ptr){ auto p = ptr; if (!mem_block_check_block(ptr)) { auto offset = *mem_block_get_magic_from_header(ptr); p = mem_block_char_ptr(ptr) - offset; } return p;}
Непосредственно резолвинг:
static void *mem_block_resolve_from_align(void *ptr){ auto p = ptr; if (!mem_block_check_block(ptr)) { auto offset = *mem_block_get_magic_from_header(ptr); p = mem_block_char_ptr(ptr) - offset; } return p;}
Такой подход повышает требования к безопасности. Нам нужно как-то убедиться что у нас правильный у нас блок. За это отвечает функция mem_block_check_block:
static inline bool mem_block_check_block(void *ptr){ if (*mem_block_get_magic_from_header(ptr) == kMagicNumber) { if ((reinterpret_cast<size_t>(ptr) % kAlignment) == 0) { if (*mem_block_header(ptr) == *mem_block_footer(ptr)) { return true; } else { ALOGE("Bad block. Header and footer are not the same"); } } return true; } else { ALOGE("Bad magic number"); } return false;}
Вот новые функции mem_free и mem_realloc:
void *mem_realloc(void *ptr, size_t new_sz){ if (!ptr) { return mem_malloc(new_sz); } void *p = mem_block_resolve_from_align(ptr); auto block = mem_malloc(new_sz); if (block) { memmove(block, p, min(new_sz, mem_block_size(p))); mem_free(p); } return block;}void mem_free(void *ptr){ if (ptr) { void *p = mem_block_resolve_from_align(ptr); if (mem_block_check_block(p)) { // проверяем что блок полностью коррктен if (mem_block_is_allocated(p)) { size_t size = mem_block_size(p); mem_block_init(p, size, kBlockFree); p = mem_block_erase_merge(p); bin_insert(mem_block_list_head(p)); } } else { ALOGE("%s(): Invalid pointer (%p)\n", __func__, ptr); } }}
Ну и вот и все, готово!
До новых встреч!
ссылка на оригинал статьи https://habr.com/ru/articles/1047178/