O Slab Allocator

Slab allocation é o design de alocador que kernels de produção usam para um caso que uma free list de propósito geral atende mal: alocar e liberar grandes quantidades de estruturas de mesmo tamanho e tipo fixo (uma task struct, um inode, um buffer de rede) em alta frequência. Heap Allocators cobre o modelo de free list de propósito geral em profundidade mas só toca em designs alternativos, sem se aprofundar em nenhum deles.

Por que um alocador de propósito geral sofre aqui

Um alocador de free list não tem noção alguma dos objetos que está distribuindo; toda requisição, independentemente do que o chamador pretende armazenar nela, compete por espaço no mesmo pool de blocos livres de tamanhos variados, o que produz dois custos que uma carga de trabalho dominada por um tipo fixo e frequentemente alocado/liberado paga repetidamente. Primeiro, satisfazer uma requisição significa percorrer a free list procurando um bloco que caiba, trabalho proporcional a quão fragmentado o heap está no momento em vez de um custo fixo; segundo, alocar e liberar objetos de mesmo tamanho numa ordem imprevisível deixa para trás um padrão espalhado de blocos livres e usados exatamente desse tamanho, fragmentação que um alocador genérico não tem como prevenir já que não tem como saber de antemão que o mesmo tamanho vai continuar recorrendo.

A ideia central

Um slab allocator contorna os dois custos dando a cada tipo de objeto distinto seu próprio cache dedicado, apoiado por um ou mais slabs, regiões contíguas de memória (comumente uma ou um pequeno número de páginas físicas) pré-divididas em slots de tamanho fixo, cada um exatamente grande o suficiente para uma instância do tipo de objeto daquele cache e nada mais.

struct kmem_cache {
    size_t   obj_size;
    void    *free_list;   // lista ligada simples entrelaçada pelos slots livres
    void    *slab_base;
};

void *kmem_cache_alloc(struct kmem_cache *cache) {
    void *obj = cache->free_list;
    if (obj) cache->free_list = *(void **)obj;  // endereço do próximo slot livre
    return obj;
}

void kmem_cache_free(struct kmem_cache *cache, void *obj) {
    *(void **)obj = cache->free_list;
    cache->free_list = obj;
}

Como todo slot num slab é idêntico em tamanho, um slot livre pode conter nada além de um ponteiro para o próximo slot livre, entrelaçando todo slot não usado no slab numa lista ligada simples sem busca alguma envolvida: alocar é retirar a cabeça da lista, e liberar é empilhar de volta nela, ambos O(1) independentemente de quantos objetos o cache atualmente contém ou quão fragmentado o resto da memória do sistema está. Isso é o que elimina por completo o custo de percorrer a free list, e como todo slot é pré-dimensionado para exatamente um objeto, não sobra vão algum de tamanho variável deixado por um objeto liberado para uma requisição de tamanho diferente preencher parcialmente ou não conseguir caber, o que é o que elimina a fragmentação que um alocador genérico sofre para essa mesma carga de trabalho.

Crescendo e encolhendo um cache

Um cache sem slots livres restantes aloca um slab novo a partir do alocador de páginas por baixo, o formata em slots do mesmo tamanho que todo outro slab naquele cache, e os entrelaça na free list da mesma forma que o primeiro slab do cache foi; um cache é portanto um número variável de slabs, crescendo conforme a demanda por aquele tipo de objeto específico aumenta. Algumas implementações vão além e mantêm objetos liberados pré-construídos: os slots de um slab são inicializados uma vez quando o slab é criado pela primeira vez, e liberar um objeto que tem um construtor não trivial (configurando locks ou list heads embutidos, por exemplo) deixa esse estado interno intacto em vez de desmontá-lo, então a próxima alocação daquele mesmo slot pula a reconstrução por completo e só precisa resetar quaisquer campos que o novo uso específico realmente exija, evitando custo repetido de construtor para objetos que ciclam por alocação e liberação rapidamente.

Notas de implementação

Um slab allocator é um complemento a um alocador de heap de propósito geral, não um substituto para ele: só faz sentido para tipos de objeto alocados com frequência suficiente, e em tamanho fixo o bastante, para justificar um cache dedicado, enquanto alocações de tamanho variável ou infrequentes continuam passando pelo alocador de propósito geral da forma que sempre passaram. Um kernel real tipicamente roda os dois lado a lado, caches dedicados para suas próprias structs de tamanho fixo alocadas com frequência, o alocador genérico de free list para tudo mais, em vez de tentar forçar toda alocação por um único mecanismo exclusivamente.

Referências

^ J. Bonwick, “The Slab Allocator: An Object-Caching Kernel Memory Allocator,” USENIX Summer Technical Conference, 1994: o artigo original do slab allocator, descrevendo seu design e uso no Solaris.

Ver também

Heap Allocators: o modelo de propósito geral que este design complementa para alocações de tamanho fixo e alta frequência em vez de substituir.