Проблема кучи

malloc / new разработаны для общего выделения памяти: произвольные размеры, произвольные времена жизни, произвольный порядок. Эта универсальность имеет цену:

Фрагментация — выделение и освобождение блоков разных размеров создаёт промежутки в куче, которые будущие запросы не могут заполнить. Система с 10 кБ свободной памяти всё равно может не справиться с запросом 1 кБ, если свободное пространство разбросано в островках по 500 байт. Долгоработающие системы (серверы, встраиваемые устройства, медиаплееры) деградируют со временем.

Недетерминизм — сколько времени занимает malloc(64)? Зависит от текущего состояния списка свободных блоков. В худшем случае обходит всю кучу. Системы реального времени не могут этого терпеть.

Накладные расходы — каждое выделение имеет служебные данные: размер, выравнивание, указатели списка свободных. Сам аллокатор — защищённая блокировкой структура данных, сериализующая все потоки.

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

Пул-аллокатор — блоки фиксированного размера

Пул-аллокатор предварительно выделяет кусок памяти и нарезает его на блоки фиксированного размера. Все блоки одного размера — нет фрагментации, O(1) выделение и освобождение.

 1template <typename T, size_t Count>
 2class PoolAllocator {
 3public:
 4    PoolAllocator() {
 5        // Строим список свободных через сырое хранилище
 6        for (size_t i = 0; i < Count - 1; ++i)
 7            blocks_[i].next = &blocks_[i + 1];
 8        blocks_[Count - 1].next = nullptr;
 9        head_ = &blocks_[0];
10    }
11
12    T* allocate() {
13        if (!head_) return nullptr;       // пул исчерпан
14        Block* b = head_;
15        head_ = b->next;
16        return reinterpret_cast<T*>(b->storage);
17    }
18
19    void deallocate(T* ptr) {
20        Block* b = reinterpret_cast<Block*>(ptr);
21        b->next = head_;
22        head_   = b;
23    }
24
25private:
26    union Block {
27        alignas(T) char storage[sizeof(T)];
28        Block* next;
29    };
30    std::array<Block, Count> blocks_;
31    Block* head_ = nullptr;
32};

Использование:

1PoolAllocator<SensorSample, 64> pool;
2
3SensorSample* s = pool.allocate();
4if (s) {
5    new (s) SensorSample{tick, voltage};  // placement new — конструируем в памяти пула
6    // ... используем s ...
7    s->~SensorSample();                   // явный деструктор
8    pool.deallocate(s);
9}

Выделение: извлечение из списка свободных — два чтения и запись указателя. O(1), всегда. Освобождение: помещение в список свободных — O(1). Фрагментация: нет. Все блоки одного размера. Ограничение: один тип на пул, фиксированное количество.

Потокобезопасный пул

Добавьте спинлок (или используйте std::atomic для указателя head с compare-exchange):

1T* allocate() {
2    std::lock_guard<std::mutex> lock(mutex_);
3    // ... то же, что выше
4}

На встраиваемых одноядерных МК вместо этого отключайте прерывания вокруг смены указателя.

STL-совместимый пул-аллокатор

Для использования с std::vector, std::list и т.д. пул должен удовлетворять именованному требованию Allocator. Минимальная версия:

 1template <typename T>
 2struct PoolAlloc {
 3    using value_type = T;
 4
 5    T* allocate(size_t n) {
 6        if (n != 1) throw std::bad_alloc{};  // пул обрабатывает только одиночные объекты
 7        return pool_.allocate();
 8    }
 9
10    void deallocate(T* p, size_t) {
11        pool_.deallocate(p);
12    }
13
14private:
15    static PoolAllocator<T, 256> pool_;  // разделяемый пул на тип
16};
17
18std::list<SensorSample, PoolAlloc<SensorSample>> samples;
19// Каждый узел выделяется из пула, не из кучи

Аллокатор-арена — линейное выделение с продвижением указателя

Арена (также bump-аллокатор или региональный аллокатор) выделяет из непрерывного блока, продвигая указатель. Индивидуальное освобождение — бесплатно; весь арен освобождается за раз.

 1class Arena {
 2public:
 3    explicit Arena(size_t capacity)
 4        : buf_(new char[capacity]), cap_(capacity), used_(0) {}
 5
 6    // Вариант без кучи для встраиваемых: передайте стековый или статический буфер
 7    Arena(char* buf, size_t cap)
 8        : buf_(buf), cap_(cap), used_(0), owned_(false) {}
 9
10    ~Arena() { if (owned_) delete[] buf_; }
11
12    void* allocate(size_t size, size_t align = alignof(std::max_align_t)) {
13        size_t offset = align_up(used_, align);
14        if (offset + size > cap_) return nullptr;  // нет места
15        used_ = offset + size;
16        return buf_ + offset;
17    }
18
19    void reset() { used_ = 0; }  // освободить всё за раз
20
21    size_t used()      const { return used_; }
22    size_t remaining() const { return cap_ - used_; }
23
24private:
25    static size_t align_up(size_t n, size_t align) {
26        return (n + align - 1) & ~(align - 1);
27    }
28
29    char*  buf_;
30    size_t cap_;
31    size_t used_ = 0;
32    bool   owned_ = true;
33};

Использование — разобрать фрейм, обработать, сбросить:

 1static char arenaBuf[4096];
 2Arena arena(arenaBuf, sizeof(arenaBuf));
 3
 4// Разбор фрейма протокола — все временные выделяются из арены
 5ParsedFrame* frame   = new (arena.allocate(sizeof(ParsedFrame))) ParsedFrame();
 6uint8_t*     payload = static_cast<uint8_t*>(arena.allocate(frame->payloadLen));
 7
 8processFrame(*frame, std::span(payload, frame->payloadLen));
 9
10arena.reset();  // всё вышеперечисленное освобождается одним сбросом указателя

Выделение: одно сложение + округление выравнивания. Быстрее malloc. Освобождение: reset() — одна запись указателя. Индивидуальных освобождений нет. Фрагментация: нет. Ограничение: объекты не должны переживать арену.

Арены на запрос (серверный паттерн)

1void handleRequest(Request& req) {
2    char buf[8192];
3    Arena arena(buf, sizeof(buf));  // стековая арена — вообще без кучи
4
5    auto response = new (arena.allocate(sizeof(Response))) Response();
6    // строим ответ, используя временные из арены
7    send(*response);
8    // арена разрушается при возврате — все выделения освобождаются неявно
9}

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

Стековый аллокатор

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

 1class StackAllocator {
 2public:
 3    explicit StackAllocator(size_t cap)
 4        : buf_(new char[cap]), cap_(cap), top_(0) {}
 5
 6    struct Marker { size_t pos; };
 7
 8    Marker mark() const { return {top_}; }
 9
10    void* allocate(size_t size, size_t align = alignof(std::max_align_t)) {
11        size_t offset = align_up(top_, align);
12        if (offset + size > cap_) return nullptr;
13        top_ = offset + size;
14        return buf_.get() + offset;
15    }
16
17    void freeToMarker(Marker m) { top_ = m.pos; }
18
19private:
20    static size_t align_up(size_t n, size_t a) { return (n + a - 1) & ~(a - 1); }
21    std::unique_ptr<char[]> buf_;
22    size_t cap_, top_;
23};

Использование — временные выделения в области видимости:

1StackAllocator sa(65536);
2
3auto m = sa.mark();             // отметить вершину стека
4void* tmp1 = sa.allocate(1024);
5void* tmp2 = sa.allocate(512);
6// использовать tmp1, tmp2 ...
7sa.freeToMarker(m);             // снять оба — O(1)

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

Встраиваемые — статическое хранилище, вообще без кучи

На МК без MMU с ограниченным flash/RAM правильный ответ — зачастую отсутствие кучи:

1// Все объекты статически выделены — линкер назначает адреса при компиляции
2static SensorPipeline   pipeline;
3static RingBuffer<uint8_t, 64> uartRxBuf;
4static PoolAllocator<Message, 16> msgPool;
5
6int main() {
7    pipeline.init();
8    // Ничего не выделяется из кучи — никогда
9}

Статическое выделение:

  • Выделение во время компоновки — нет затрат времени выполнения
  • Общее использование памяти видно в map-файле
  • Фрагментация невозможна
  • Ошибка линкера (не крэш времени выполнения) при превышении RAM

Комбинируйте статическое выделение с пулом для объектов с переменным количеством:

1// Не более 16 сообщений одновременно — пул выделяется из статического хранилища
2static char msgBuf[sizeof(Message) * 16 + alignof(Message) * 16];
3static Arena msgArena(msgBuf, sizeof(msgBuf));

Выбор аллокатора

Аллокатор Стоимость выделения Стоимость освобождения Фрагментация Применение
malloc/new O(n) O(n) Да Общее назначение
Пул O(1) O(1) Нет Объекты фиксированного размера, много времён жизни
Арена O(1) O(1) пакетно Нет Временные на время запроса
Стек O(1) O(1) LIFO Нет Временные кадра/области видимости
Статический 0 (время компиляции) Нет Нет Известное количество встраиваемых объектов

Обнаружение проблем с кучей

Valgrind (Linux/настольный) обнаруживает повреждение кучи, использование после освобождения, двойное освобождение и утечки:

1valgrind --leak-check=full --track-origins=yes ./your_binary

Address Sanitizer (Clang/GCC) — быстрее valgrind, те же классы ошибок:

1clang++ -fsanitize=address -g your.cpp -o your_binary
2./your_binary

Измерение использования кучи во встраиваемых — проверка конца кучи во время выполнения:

1// Newlib / FreeRTOS
2extern char _end;           // начало кучи (символ линкера)
3void* heapTop = sbrk(0);   // текущая граница
4size_t used = (size_t)heapTop - (size_t)&_end;

Или используйте xPortGetFreeHeapSize() / xPortGetMinimumEverFreeHeapSize() из FreeRTOS для отслеживания максимальных отметок.

Итоги

  • Стандартная куча склонна к фрагментации и недетерминирована — избегайте во встраиваемых и высокопроизводительных путях
  • Пул-аллокатор: O(1) выделение/освобождение, нет фрагментации, фиксированный тип и количество
  • Аллокатор-арена: продвижение указателя, пакетное освобождение за раз — идеально для временных на время запроса
  • Стековый аллокатор: LIFO-освобождение в дополнение к пакетному — покадровые выделения в играх/графике
  • Статическое выделение: нулевые затраты времени выполнения, размер проверяется при компоновке — стандарт для встраиваемых

Что дальше