Пул объектов: паттерн эффективного управления памятью

Введение

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

Для высоконагруженных систем, чтобы эффективно выделять и освобождать память под объекты без лишних вызовов malloc/free и потенциальных системных вызовов, используют паттерн пулов объектов.

Этот паттерн особенно хорошо подходит для следующих систем и сценариев:

1. Системы реального времени (промышленные контроллеры, автопилоты) – здесь важна предсказуемость времени выполнения операций выделения памяти под объекты.

2. Встраиваемые системы (микроконтроллеры, устройства с ограниченным объёмом RAM) – пул позволяет избежать фрагментации и полностью контролировать расход памяти.

3. Игровые движки – часто требуют быстрого создания/уничтожения большого количества однотипных объектов.

4. Высоконагруженные сетевые серверы (обработчики запросов, прокси, фаерволы) – во время обработки трафика важно не тратить время на системные вызовы при выделении памяти под соединения, пакеты, сессии.

В статье будет описан один из вариантов реализации этого паттерна на языке C.

Как это работает?

Весь необходимый объём памяти для пула выделяется заранее, во время его создания. Размер хранимых объектов задаётся при инициализации пула, также фиксируется максимальное количество хранимых объектов. В процессе работы из выделенного участка памяти берутся свободные сегменты под объекты, если свободных сегментов нет возвращается NULL. Когда нужно вернуть сегмент в пул, он помечается как свободный. Во время удаления пула освобождается вся выделенная память. Таким образом, мы выделяем и освобождаем память только при создании и удалении пула.

Сложность операций работы с пулом

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

Визуализация работы пула

В самом начале имеется пул объектов и стек всех свободных сегментов. Стек заполняется индексами сверху вниз.

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

Аналогичным образом при повторном вызове get_seg.

Когда нужно вернуть элемент, вычисляется его позиция и помещается на вершину стека.

Также при повторном возврате объекта.

Описание кода

Структура заголовка стека:

typedef struct stack_header_s {
    size_t n_obj_;          // Количество элементов
    size_t head_indx_;      // Индекс вершины стека
    unsigned int obj_sz_;   // Размер хранимого объекта
} stack_header_t;

#define INVALID_INDX (~(0u)) // Если head_indx_ == INVALID_INDX — стек пуст

Заголовок структуры размещается перед данными, что позволяет не привязываться к конкретному типу.

Функция создания стека:

void* create_stack(size_t n_obj, unsigned int obj_size, int set_zero) {
    size_t msz = n_obj * obj_size + sizeof(stack_header_t);
    stack_header_t *sh = malloc(msz);

    if (sh == NULL) 
        return NULL;

    if (set_zero)
        memset(sh, 0, msz);

    sh->head_indx_ = INVALID_INDX;
    sh->n_obj_ = n_obj;
    sh->obj_sz_ = obj_size;

    return sh + 1; // указатель на данные после заголовка
}

Функция удаления стека:

void destroy_stack(void *stack) {
    stack_header_t *sh = ((stack_header_t*)(stack)) - 1;
    free(sh);
}

Функция добавления элемента в стек:

void* push_obj(void* stack, void* obj) {
    stack_header_t *sh = ((stack_header_t*)(stack)) - 1;

    if (sh->head_indx_ != INVALID_INDX && sh->head_indx_ + 1 == sh->n_obj_)
        return NULL;

    if (sh->head_indx_ == INVALID_INDX)
        sh->head_indx_ = 0;
    else
        ++sh->head_indx_;

    unsigned char* obj_addr = ((unsigned char*)(stack)) + (sh->head_indx_ * sh->obj_sz_);
    memcpy(obj_addr, obj, sh->obj_sz_);

    return obj_addr;
}

Функция удаления элемента из стека (без возврата значения):

void pop_obj(void* stack) {
    stack_header_t *sh = ((stack_header_t*)(stack)) - 1;

    if (sh->head_indx_ == INVALID_INDX)
        return; // стек пуст — ничего не делаем

    if (sh->head_indx_ == 0) 
        sh->head_indx_ = INVALID_INDX;
    else
        --sh->head_indx_;
}

Получение указателя на верхний элемент стека (без удаления):

void* peek_obj(void* stack) {
    stack_header_t *sh = ((stack_header_t*)(stack)) - 1;

    if (sh->head_indx_ == INVALID_INDX)
        return NULL;
    
    return ((unsigned char *)stack) + (sh->head_indx_ * sh->obj_sz_);
}

Структура заголовка пула:

typedef struct pool_obj_header_s {
    unsigned int *free_indxs_; // стек со свободными индексами
    unsigned int obj_sz_;      // размер хранимых объектов
    size_t n_obj_;             // количество сегментов под хранение объектов
} pool_obj_header_t;

Функция создания пула (версия без учёта выравнивания — см. раздел ниже):

void* create_pool(size_t n_obj, unsigned int obj_size, int set_zero) {
    size_t msz = n_obj * obj_size + sizeof(pool_obj_header_t);
    pool_obj_header_t *ph = malloc(msz);

    if (ph == NULL) 
        return NULL;

    if (set_zero)
        memset(ph, 0, msz);

    ph->free_indxs_ = create_stack(n_obj, sizeof(unsigned int), 1);

    if (ph->free_indxs_ == NULL) {
        free(ph);
        return NULL;
    }

    ph->n_obj_ = n_obj;
    ph->obj_sz_ = obj_size;

    for (unsigned int i = 0; i < n_obj; ++i) {
        push_obj(ph->free_indxs_, &i);
    }

    return ph + 1; // указатель на область данных
}

Функция удаления пула:

void destroy_pool(void *pool) {
    pool_obj_header_t *ph = ((pool_obj_header_t *)pool) - 1;
    destroy_stack(ph->free_indxs_);
    free(ph);
}

Функция освобождения сегмента:

void put_seg(void* pool, void* obj) {
    pool_obj_header_t *ph = ((pool_obj_header_t *)pool) - 1;

    // Обязательно приводим к unsigned char* для корректной арифметики
    unsigned int obj_indx = ((unsigned char*)obj - (unsigned char*)pool) / ph->obj_sz_;

    push_obj(ph->free_indxs_, &obj_indx);
}

Функция взятия свободного сегмента:

void* get_seg(void* pool) {
    pool_obj_header_t *ph = ((pool_obj_header_t *)pool) - 1;

    unsigned int *free_indx_ptr = peek_obj(ph->free_indxs_);
    if (free_indx_ptr == NULL)
        return NULL;

    unsigned int idx = *free_indx_ptr; // сохраняем значение до pop
    pop_obj(ph->free_indxs_);

    return ((unsigned char*)pool) + idx * ph->obj_sz_;
}

Почему важно подумать о выравнивании памяти

Процессоры и операционные системы накладывают ограничения на адреса, по которым можно читать и писать данные определённых типов. Например, переменная типа double на многих архитектурах должна быть выровнена по адресу, кратному 8. Если обратиться к такой переменной по невыровненному адресу, может произойти:

1. Замедление доступа (в несколько раз на x86).

2. Аппаратное исключение (на ARM, SPARC, некоторых других архитектурах).

В текущей реализации память выделяется одним блоком через malloc, который возвращает адрес, подходящий для любого стандартного типа (то есть выровненный по max_align_t, обычно 8 или 16 байт). Однако сам пул разбивает этот блок на сегменты размером obj_sz_ байт. Если obj_sz_ не кратен требуемому выравниванию для хранимых объектов, то, начиная с некоторого сегмента, адреса перестанут быть правильно выровненными.

Пример: Пусть max_align_t требует выравнивания 8, а obj_sz_ = 12. Первый объект получит адрес, который кратен 8. Второй объект — указатель на pool + 12, он уже не кратен 8, что может вызвать проблемы при попытке доступа к полю типа double.

Если тип хранимых данных не требует выравнивания, то можно оставить текущую реализацию.

Недостатки данного подхода к реализации пула

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

2. Текущая реализация — непотокобезопасна. Для использования в многопоточных программах необходимо добавить синхронизацию в get_seg и put_seg или использовать паттерн «per thread data», о котором пойдет речь в следующей статье.

Заключение

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