Приветствую читатель!
Для тех кто со мной впервые вот оглавление:
Код лежит тут
Подразумевается что читатель знаком с архитектурой аллокатора из части 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;
}
// возвращает адрес памяти выровненный по границе alignment
void *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);
}
}
}Ну и вот и все, готово!
До новых встреч!