Приветствую читатель!

Для тех кто со мной впервые вот оглавление:

Часть 1

Часть 2

Часть 3

Код лежит тут

Подразумевается что читатель знаком с архитектурой аллокатора из части 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);
        }
    }
}

Ну и вот и все, готово!

До новых встреч!