Memory pools e allocators customizados

1. Introdução aos Alocadores Customizados

A alocação dinâmica de memória em C, tradicionalmente feita com malloc e free, apresenta problemas conhecidos em sistemas de alto desempenho: fragmentação de memória, latência imprevisível e overhead de gerenciamento. Em aplicações como jogos, sistemas embarcados e processamento de áudio/vídeo em tempo real, esses problemas podem ser críticos.

Os alocadores customizados surgem como alternativa para controlar como, quando e de onde a memória é obtida. Os principais tipos são:

  • Alocador linear (arena): aloca sequencialmente, sem desalocação individual
  • Memory pool: gerencia blocos de tamanho fixo com free list
  • Stack allocator: aloca e desaloca em ordem LIFO
  • Slab allocator: especializado para objetos de tamanho fixo com inicialização

A escolha envolve trade-offs entre velocidade (alocadores lineares são os mais rápidos), flexibilidade (pools permitem desalocação individual) e footprint de memória (alocadores slab reduzem desperdício).

2. Implementação de um Memory Pool Simples

Um memory pool gerencia blocos de memória de tamanho fixo. A implementação mais comum usa uma lista encadeada de blocos livres (free list).

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct MemoryPool {
    void *memory;           // Bloco contínuo de memória
    size_t block_size;      // Tamanho de cada bloco (alinhado)
    size_t block_count;     // Número total de blocos
    void *free_list;        // Ponteiro para o primeiro bloco livre
    uint8_t *bitmap;        // Opcional: bitmap para rastrear alocações
} MemoryPool;

MemoryPool* pool_create(size_t block_size, size_t block_count) {
    MemoryPool *pool = malloc(sizeof(MemoryPool));
    if (!pool) return NULL;

    // Alinhar block_size para evitar problemas
    block_size = (block_size + 7) & ~7;

    pool->block_size = block_size;
    pool->block_count = block_count;
    pool->memory = malloc(block_size * block_count);
    pool->bitmap = calloc((block_count + 7) / 8, 1);

    if (!pool->memory || !pool->bitmap) {
        free(pool->memory);
        free(pool->bitmap);
        free(pool);
        return NULL;
    }

    // Inicializar free list: cada bloco aponta para o próximo
    for (size_t i = 0; i < block_count - 1; i++) {
        void **current = (void**)((char*)pool->memory + i * block_size);
        *current = (char*)pool->memory + (i + 1) * block_size;
    }
    void **last = (void**)((char*)pool->memory + (block_count - 1) * block_size);
    *last = NULL;
    pool->free_list = pool->memory;

    return pool;
}

void* pool_alloc(MemoryPool *pool) {
    if (!pool->free_list) return NULL;  // Pool esgotado

    void *block = pool->free_list;
    pool->free_list = *(void**)block;

    // Marcar no bitmap (opcional, para depuração)
    size_t index = ((char*)block - (char*)pool->memory) / pool->block_size;
    pool->bitmap[index / 8] |= (1 << (index % 8));

    return block;
}

void pool_free(MemoryPool *pool, void *block) {
    if (!block) return;

    // Verificar se o bloco pertence ao pool
    char *base = (char*)pool->memory;
    char *end = base + pool->block_size * pool->block_count;
    if ((char*)block < base || (char*)block >= end) return;

    // Limpar bitmap
    size_t index = ((char*)block - base) / pool->block_size;
    pool->bitmap[index / 8] &= ~(1 << (index % 8));

    // Retornar bloco à free list
    *(void**)block = pool->free_list;
    pool->free_list = block;
}

void pool_destroy(MemoryPool *pool) {
    if (pool) {
        free(pool->memory);
        free(pool->bitmap);
        free(pool);
    }
}

3. Arena Allocator (Alocador Linear)

O alocador linear (ou arena) é o mais simples e rápido: mantém um ponteiro que avança a cada alocação. A desalocação só ocorre quando toda a arena é resetada.

typedef struct Arena {
    char *memory;
    size_t size;
    size_t offset;
} Arena;

Arena arena_create(size_t size) {
    Arena arena;
    arena.memory = malloc(size);
    arena.size = size;
    arena.offset = 0;
    return arena;
}

void* arena_alloc(Arena *arena, size_t size) {
    // Alinhar para 8 bytes
    size = (size + 7) & ~7;

    if (arena->offset + size > arena->size) return NULL;

    void *ptr = arena->memory + arena->offset;
    arena->offset += size;
    return ptr;
}

void arena_reset(Arena *arena) {
    arena->offset = 0;
}

void arena_destroy(Arena *arena) {
    free(arena->memory);
    arena->memory = NULL;
    arena->size = 0;
    arena->offset = 0;
}

Casos de uso típicos: processamento de frames em jogos (cada frame usa uma arena nova), parsers temporários (XML, JSON), alocações durante uma requisição HTTP.

4. Slab Allocator para Objetos de Tamanho Fixo

O slab allocator é otimizado para alocar muitos objetos do mesmo tipo. Diferente do pool simples, ele suporta construtores/destrutores e reduz ainda mais a fragmentação.

typedef struct Slab {
    void *objects;          // Array de objetos
    size_t object_size;     // Tamanho de cada objeto
    size_t capacity;        // Capacidade do slab
    size_t used;            // Objetos atualmente em uso
    struct Slab *next;      // Próximo slab (para crescimento)
} Slab;

typedef struct SlabCache {
    size_t object_size;
    size_t slab_capacity;   // Objetos por slab
    Slab *partial_slabs;    // Slabs parcialmente usados
    Slab *full_slabs;       // Slabs completamente cheios
    Slab *empty_slabs;      // Slabs vazios (reutilizáveis)
    void (*constructor)(void *obj);
    void (*destructor)(void *obj);
} SlabCache;

SlabCache* slab_cache_create(size_t object_size, 
                             void (*ctor)(void*), 
                             void (*dtor)(void*)) {
    SlabCache *cache = malloc(sizeof(SlabCache));
    if (!cache) return NULL;

    cache->object_size = (object_size + 7) & ~7;
    cache->slab_capacity = 4096 / cache->object_size; // Slabs de 4KB
    if (cache->slab_capacity < 8) cache->slab_capacity = 8;

    cache->partial_slabs = NULL;
    cache->full_slabs = NULL;
    cache->empty_slabs = NULL;
    cache->constructor = ctor;
    cache->destructor = dtor;

    return cache;
}

void* slab_alloc(SlabCache *cache) {
    // Buscar um slab com espaço disponível
    if (!cache->partial_slabs) {
        // Criar novo slab
        Slab *slab = malloc(sizeof(Slab));
        slab->objects = malloc(cache->object_size * cache->slab_capacity);
        slab->object_size = cache->object_size;
        slab->capacity = cache->slab_capacity;
        slab->used = 0;
        slab->next = cache->partial_slabs;
        cache->partial_slabs = slab;

        // Inicializar objetos com construtor
        for (size_t i = 0; i < slab->capacity; i++) {
            if (cache->constructor) {
                cache->constructor((char*)slab->objects + i * slab->object_size);
            }
        }
    }

    Slab *slab = cache->partial_slabs;
    void *obj = (char*)slab->objects + slab->used * slab->object_size;
    slab->used++;

    if (slab->used == slab->capacity) {
        // Mover para full_slabs
        cache->partial_slabs = slab->next;
        slab->next = cache->full_slabs;
        cache->full_slabs = slab;
    }

    return obj;
}

void slab_free(SlabCache *cache, void *obj) {
    // Encontrar o slab que contém o objeto
    Slab *slab = cache->partial_slabs;
    // Lógica simplificada: na prática, usa-se um mapa de slabs
    // ...
    if (cache->destructor) cache->destructor(obj);
}

A principal vantagem sobre o memory pool simples é que objetos pré-inicializados reduzem o overhead de construção repetida.

5. Alocadores Hierárquicos e Region-based

Alocadores hierárquicos permitem que um alocador pai gerencie a memória de múltiplos alocadores filhos. Quando o pai é destruído, todos os filhos são automaticamente liberados.

typedef struct RegionAllocator {
    struct RegionAllocator *parent;
    Arena *arenas;          // Lista de arenas gerenciadas
    size_t arena_count;
} RegionAllocator;

RegionAllocator* region_create(RegionAllocator *parent) {
    RegionAllocator *region = malloc(sizeof(RegionAllocator));
    region->parent = parent;
    region->arenas = NULL;
    region->arena_count = 0;
    return region;
}

void* region_alloc(RegionAllocator *region, size_t size) {
    // Alocar de uma arena existente ou criar nova
    if (region->arena_count == 0 || 
        /* arena atual sem espaço */) {
        // Criar nova arena de 64KB
        Arena *new_arena = malloc(sizeof(Arena));
        *new_arena = arena_create(65536);
        new_arena->next = region->arenas;
        region->arenas = new_arena;
        region->arena_count++;
    }
    return arena_alloc(region->arenas, size);
}

void region_destroy(RegionAllocator *region) {
    // Liberar todas as arenas filhas
    Arena *current = region->arenas;
    while (current) {
        Arena *next = current->next;
        arena_destroy(current);
        free(current);
        current = next;
    }
    free(region);
}

Uso típico: processamento de uma requisição web onde cada etapa (parse, validação, transformação) pode ter seu próprio sub-alocador.

6. Integração com o Sistema de Tipos e Macros

Macros bem definidas tornam o uso de alocadores customizados mais seguro e expressivo:

#define POOL_ALLOC(pool, type) \
    (type*)pool_alloc(pool)

#define POOL_FREE(pool, ptr) \
    pool_free(pool, (void*)ptr)

#define ARENA_ALLOC(arena, type, count) \
    (type*)arena_alloc(arena, sizeof(type) * (count))

// Uso com verificação de alinhamento
#define ALIGNED_ALLOC(arena, type, alignment) \
    ({ \
        size_t _align = (alignment); \
        size_t _size = sizeof(type); \
        size_t _offset = _align - ((uintptr_t)arena->memory + arena->offset) % _align; \
        if (_offset != _align) arena->offset += _offset; \
        (type*)arena_alloc(arena, _size); \
    })

// Padrão com goto cleanup
#define WITH_ARENA(arena_var, size) \
    for (Arena arena_var = arena_create(size), *_cleanup = &arena_var; \
         _cleanup; \
         arena_destroy(&arena_var), _cleanup = NULL)

7. Benchmarking e Depuração de Alocadores Customizados

Para avaliar alocadores customizados, métricas importantes incluem:

  • Throughput: alocações por segundo (micro-benchmarks)
  • Overhead de memória: bytes extras por alocação
  • Fragmentação: razão entre maior bloco livre e memória total

Ferramentas como Valgrind podem ser adaptadas com wrappers:

// Wrapper para depuração com Valgrind
#include <valgrind/memcheck.h>

void* debug_pool_alloc(MemoryPool *pool) {
    void *ptr = pool_alloc(pool);
    if (ptr) {
        VALGRIND_MALLOCLIKE_BLOCK(ptr, pool->block_size, 0, 0);
    }
    return ptr;
}

void debug_pool_free(MemoryPool *pool, void *ptr) {
    VALGRIND_FREELIKE_BLOCK(ptr, 0);
    pool_free(pool, ptr);
}

Armadilhas comuns:
- Alinhamento: structs com _Alignas podem quebrar em pools mal projetados
- Race conditions: pools compartilhados entre threads precisam de mutex ou operações atômicas
- Double-free: a free list pode corromper se o mesmo bloco for liberado duas vezes

8. Considerações Finais e Boas Práticas

Guia de decisão rápida:
- Poucas alocações grandes e variáveis → malloc padrão
- Muitas alocações temporárias → arena allocator
- Objetos de tamanho fixo frequentes → memory pool ou slab
- Hierarquia de lifetimes → alocadores regionais

Cuidados com portabilidade:
- Alinhamento: use max_align_t ou _Alignas (C11)
- Endianness: raramente afeta alocadores, mas cuidado com bitmaps
- Arquiteturas: ponteiros de 64 bits exigem alinhamento a 8 bytes

Tópicos avançados:
- Atomics para pools thread-safe (C11 _Atomic)
- SIMD para inicialização em lote de objetos
- Alocadores lock-free baseados em CAS

Alocadores customizados não substituem malloc em todos os casos, mas são ferramentas essenciais para sistemas que exigem desempenho previsível e controle fino sobre memória.

Referências