Полезность распределителей фиксированных блоков с годами не меняется, поскольку на некоторых устройствах нельзя использовать общую кучу. Общий, хорошо спроектированный распределитель фиксированных блоков открывает возможности реализации приложений, предлагая динамическое распределение памяти в системах, где использование кучи запрещено.

Сегодня мы представим версию распределителя на языке C с уникальными функциями, подходящими для встраиваемых устройств или для других целей.

Представленное здесь решение будет:

• быстрее, чем куча;
• простое в использовании;
• потокобезопасно;
• поддерживать фиксированные блочные версии malloc, free, realloc и calloc
• использовать минимальное пространство кода
• выполняться в назначенное время
• устранять ошибки фрагментации памяти кучи;
• не будет требовать дополнительных затрат памяти (за исключением нескольких байтов статической памяти)
• управлять выравниванием памяти
• автоматически распределять переменный размер блока в зависимости от спроса (а-ля malloc)

Два простых модуля C, которые распределяют и возвращают память, обеспечат все вышеупомянутые преимущества, в чем вы убедитесь далее.

Бэкграунд

Пользовательские распределители фиксированных блоков памяти используются для решения как минимум двух типов проблем, связанных с памятью. Во-первых, распределение или отмена распределения кучи может быть медленным и недетерминированным. Вы никогда не знаете, сколько времени займет менеджер памяти. Во-вторых, устранить возможность ошибки выделения памяти, вызванной фрагментированной кучи, - серьезная проблема, особенно в системах критически важных типов.

Даже если система не считается критически важной, некоторые встроенные системы могут работать в течение нескольких недель или лет без перезагрузки. В зависимости от моделей распределения и реализации кучи долгосрочное использование кучи может привести к сбоям кучи.

fb_allocator

Каждый экземпляр fb_allocator обрабатывает один размер блока. Интерфейс показан ниже:

void ALLOC_Init(void);
void ALLOC_Term(void);
void* ALLOC_Alloc(ALLOC_HANDLE hAlloc, size_t size);
void* ALLOC_Calloc(ALLOC_HANDLE hAlloc, size_t num, size_t size);
void ALLOC_Free(ALLOC_HANDLE hAlloc, void* pBlock);

ALLOC_Init () вызывается один раз при запуске и ALLOC_Term () при завершении работы. Каждый из оставшихся API работает так же, как и CRT-аналоги; ALLOC_Alloc () выделяет память, а ALLOC_Free () освобождает.

Экземпляр fb_allocator создается с помощью макроса ALLOC_DEFINE в области видимости файла. Распределитель TestAlloc ниже определяет распределитель фиксированных блоков с максимум пятью 16-байтовыми блоками.

ALLOC_DEFINE(TestAlloc, 16, 5);

Распределить 16-байтовый блок просто.

void* data = ALLOC_Alloc(TestAlloc, 16);

Отмените распределение блока когда закончите.

ALLOC_Free(TestAlloc, data);

x_allocator

Модуль x_allocator обрабатывает блоки памяти нескольких размеров, используя два или более экземпляров fb_allocator; один fb_allocator на размер блока. Во время выделения x_allocator возвращает блок, калиброванный от одного из экземпляров fb_allocator на основе запрошенного размера вызывающего. API x_allocator показан ниже:

void* XALLOC_Alloc(XAllocData* self, size_t size);
void XALLOC_Free(void* ptr);
void* XALLOC_Realloc(XAllocData* self, void *ptr, size_t new_size);
void* XALLOC_Calloc(XAllocData* self, size_t num, size_t size);

Пользователи x_allocator обычно создают тонкий модуль-обертку, который, во-первых, определяет два или более экземпляров fb_allocator и, во вторых - предоставляет пользовательский API для доступа к памяти x_allocator. Это проще объяснить на простом примере.

my_allocator

Допустим, мы хотим, чтобы фиксированный распределитель блоков распределял блоки двух размеров: 32 и 128. Мы назовем его my_allocator, и API показан ниже:

void* MYALLOC_Alloc(size_t size);
void MYALLOC_Free(void* ptr);
void* MYALLOC_Realloc(void *ptr, size_t new_size);
void* MYALLOC_Calloc(size_t num, size_t size);

Реализация создает несколько экземпляров fb_allocator; один для обработки каждого желаемого размера блока. В этом случае мы допустим не более десяти 32-байтовых блоков и пять 128-байтовых блоков.

#include "my_allocator.h"
#include "x_allocator.h"

// Maximum number of blocks for each size
#define MAX_32_BLOCKS   10
#define MAX_128_BLOCKS  5

// Define size of each block including meta data overhead
#define BLOCK_32_SIZE     32 + XALLOC_BLOCK_META_DATA_SIZE
#define BLOCK_128_SIZE    128 + XALLOC_BLOCK_META_DATA_SIZE

// Define individual fb_allocators
ALLOC_DEFINE(myDataAllocator32, BLOCK_32_SIZE, MAX_32_BLOCKS)
ALLOC_DEFINE(myDataAllocator128, BLOCK_128_SIZE, MAX_128_BLOCKS)

// An array of allocators sorted by smallest block first
static ALLOC_Allocator* allocators[] = {
    &myDataAllocator32Obj,
    &myDataAllocator128Obj
};

#define MAX_ALLOCATORS   (sizeof(allocators) / sizeof(allocators[0]))

static XAllocData self = { allocators, MAX_ALLOCATORS };

Теперь простые однострочные функции-оболочки предоставляют доступ к базовому модулю x_allocator.

void* MYALLOC_Alloc(size_t size)
{
    return XALLOC_Alloc(&self, size);
}

void MYALLOC_Free(void* ptr)
{
    XALLOC_Free(ptr);
}

void* MYALLOC_Realloc(void *ptr, size_t new_size)
{
    return XALLOC_Realloc(&self, ptr, new_size);
}

void* MYALLOC_Calloc(size_t num, size_t size)
{
    return XALLOC_Calloc(&self, num, size);
}

Когда вызывающая сторона вызывает MYALLOC_Alloc () размером от 1 до 32, возвращается 32-байтовый блок. Если запрашиваемый размер составляет от 33 до 128, предоставляется 128-байтовый блок. MYALLOC_Free () возвращает блок в исходный экземпляр fb_allocator. Таким образом, коллекция распределителей памяти фиксированных блоков группируется вместе, обеспечивая блоки памяти переменного размера во время выполнения в зависимости от требований приложения. Образец шаблона оболочки используется снова и снова, предлагая группы блоков памяти для определенных целей в системе.

Детали реализации

Большая часть реализации распределителя относительно проста. Тем не менее, поясним несколько деталей, чтобы помочь с ключевыми понятиями.

Cписок свободной памяти fb_allocator

Это удобный метод для объединения блоков в свободном списке без использования дополнительного хранилища для указателей. После того, как пользователь вызывает ALLOC_Free (), фиксированный блок памяти больше не используется и освобождается для использования для других целей, таких как следующий указатель. Поскольку модуль fb_allocator должен хранить удаленные блоки, мы помещаем следующий указатель списка в это неиспользуемое в настоящее время пространство блоков. Когда блок повторно используется приложением, указатель больше не нужен и будет перезаписан объектом пользователя. Таким образом, нет никаких накладных расходов на хранение для каждого экземпляра, связанных с объединением блоков.

Список свободной памяти фактически реализован как односвязный список, но код только добавляет или удаляет из первого элемента, поэтому поведение соответствует стеку. Использование стека делает распределение или его отмену действительно быстрым и детерминированным. Нет цикла поиска свободного блока - просто нажмите или вытолкните блок и вперед.

Использование свободного пространства объектов в качестве памяти для соединения блоков означает, что объект должен быть достаточно большим, чтобы содержать указатель. Макрос ALLOC_BLOCK_SIZE обеспечивает соблюдение минимального размера.

Выравнивание памяти fb_allocator

Некоторые встроенные системы требуют, чтобы память была выровнена по определенной границе байта. Поскольку память распределителя представляет собой непрерывный статический байтовый массив, начало блоков на невыровненной границе может вызвать аппаратное исключение на некоторых процессорах. Например, 13-байтовые блоки вызовут проблему, если требуется 4-байтовое выравнивание. Измените ALLOC_MEM_ALIGN на желаемую границу байта. Размер блока будет округлен до ближайшей ближайшей выровненной границы.

Метаданные x_allocator

Реализация x_allocator добавляет 4 байта метаданных на блок. Например, если пользователю требуются 32-байтовые блоки, x_allocator фактически использует 36-байтовые блоки. Дополнительные 4 байта используются, чтобы скрыть указатель fb_allocator внутри блока (при условии, что указатель имеет размер 4 байта).

При удалении памяти x_allocator требуется исходный экземпляр fb_allocator, чтобы запрос на освобождение можно было направить на правильный экземпляр fb_allocator для обработки. В отличие от XALLOC_Alloc (), XALLOC_Free () не принимает размер и использует только аргумент void *. Таким образом, XALLOC_Alloc () фактически скрывает указатель на fb_allocator в неиспользуемой части блока памяти, добавляя дополнительные 4 байта к запросу. Вызывающая сторона получает указатель на клиентскую область блока, где скрытый указатель fb_allocator не перезаписывается.

void* XALLOC_Alloc(XAllocData* self, size_t size)
{
    ALLOC_Allocator* pAllocator;
    void* pBlockMemory = NULL;
    void* pClientMemory = NULL;

    ASSERT_TRUE(self);

    // Get an allocator instance to handle the memory request
    pAllocator = XALLOC_GetAllocator(self, size);

    // An allocator found to handle memory request?
    if (pAllocator)
    {
        // Get a fixed memory block from the allocator instance
        pBlockMemory = ALLOC_Alloc(pAllocator, size + XALLOC_BLOCK_META_DATA_SIZE);
        if (pBlockMemory)
        {
            // Set the block ALLOC_Allocator* ptr within the raw memory block region
            pClientMemory = XALLOC_PutAllocatorPtrInBlock(pBlockMemory, pAllocator);
        }
    }
    else
    {
        // Too large a memory block requested
        ASSERT();
    }

    return pClientMemory;
} 

Когда вызывается XALLOC_Free (), указатель распределителя извлекается из блока памяти, поэтому для освобождения блока можно вызвать правильный экземпляр fb_allocator.

void XALLOC_Free(void* ptr)
{
    ALLOC_Allocator* pAllocator = NULL;
    void* pBlock = NULL;

    if (!ptr)
        return;

    // Extract the original allocator instance from the caller's block pointer
    pAllocator = XALLOC_GetAllocatorPtrFromBlock(ptr);
    if (pAllocator)
    {
        // Convert the client pointer into the original raw block pointer
        pBlock = XALLOC_GetBlockPtr(ptr);

        // Deallocate the fixed memory block
        ALLOC_Free(pAllocator, pBlock);
    }
}

Бенчмаркинг

Сравнительный анализ производительности распределителя и общей кучи на ПК с Windows показывает, насколько быстрым является код. Базовый тест распределения и освобождения блоков размером 20000, 4096 и 2048 в несколько чередующемся режиме проверяет улучшение скорости. Смотрите прилагаемый исходный код для точного алгоритма: Download

Время распределения Windows в миллисекундах

Windows использует кучу отладки при выполнении в отладчике. Куча отладки добавляет дополнительные проверки безопасности, замедляя ее производительность. Куча релиза намного быстрее, поскольку проверки отключены. Кучи отладки можно отключить в Visual Studio, установив _NO_DEBUG_HEAP = 1 в параметре проекта «Debugging > Environment».

Этот тест очень прост, и более реалистичный сценарий с различными размерами блоков и случайными интервалами new / delete может дать разные результаты. Тем не менее, основной момент хорошо иллюстрируется; диспетчер памяти медленнее, чем распределитель, и сильно зависит от реализации платформы.

Fb_allocator использует статический пул памяти и не полагается на кучу. Это быстрое время выполнения около 4 мс после заполнения списка свободных блоков. 22,6 мс на fb_allocator Run 1 учитывает разбиение фиксированного пула памяти на отдельные блоки при первом запуске.

X_allocator, используемый в модуле bm_allocator, немного медленнее при ~ 7 мс, поскольку у него есть издержки для распределения блоков разного размера или его отмены, тогда как fb_allocator поддерживает только один размер блока.

По сравнению с общей кучей Windows, fb_allocator примерно в 8 раз быстрее, а x_allocator примерно в 5 раз быстрее. На встроенных устройствах было замечено увеличение скорости в 15 раз по сравнению с общей кучей.

Потоковая безопасность

Макросы LK_LOCK и LK_UNLOCK в модуле LockGuard реализуют программные блокировки, необходимые для обеспечения безопасности потоков. Обновите реализацию блокировки в соответствии с требованиями операционной системы вашей платформы.

Заключение

Представленный здесь распределитель памяти с фиксированными блоками на основе C подходит для любой системы C или C ++.

Используйте fb_allocator всякий раз, когда вам нужно выделить один размер блока. Используйте x_allocator, когда требуется дозирование блоков нескольких размеров. Создайте несколько оболочек x_allocator для разделения пулов памяти в зависимости от предполагаемого использования.

Если у вас есть приложение, которое действительно забивает кучу и вызывает медленную производительность, или если вы беспокоитесь о сбое фрагментированной кучи, интеграция fb_allocator и x_allocator может помочь решить эти проблемы. Реализация была сведена к минимуму, облегчая использование даже на самых маленьких встроенных системах.

No Comments