Pool allocators

Si todos los objetos miden lo mismo, el problema difícil de la asignación desaparece. No hay que buscar un hueco del tamaño adecuado porque todos los huecos sirven, y no hay fragmentación externa porque no existen huecos de tamaños incompatibles. Lo que queda es un asignador que cabe en veinte líneas, responde en tiempo constante acotado y no gasta un solo byte extra por objeto: el pool es lo que ocurre cuando cambias generalidad por una restricción que tu programa ya cumplía.

La lista libre intrusiva

La idea central es un juego de manos: mientras una ranura está libre, su contenido no le importa a nadie, así que el asignador puede usar esos mismos bytes para guardar el puntero a la siguiente ranura libre. La lista de libres vive dentro de la memoria que administra y no cuesta ni un byte aparte.

typedef struct Ranura Ranura;
struct Ranura { Ranura *siguiente; };      // solo valido mientras esta libre

typedef struct {
    Ranura        *libres;
    unsigned char *bloque;
    size_t         tam_ranura;
} Pool;

void *pool_alloc(Pool *p) {
    Ranura *r = p->libres;
    if (r == nullptr) return nullptr;      // o pedir otro bloque al sistema
    p->libres = r->siguiente;
    return r;
}

void pool_free(Pool *p, void *obj) {
    Ranura *r = obj;
    r->siguiente = p->libres;
    p->libres = r;
}

Ambas operaciones son tres accesos a memoria y ninguna rama de búsqueda: coste constante con cota superior real, no amortizada. Esa cota es lo que hace del pool el asignador dinámico admisible en sistemas de tiempo real duro, donde malloc queda descartado no por lento sino por carecer de peor caso demostrable.

La inicialización consiste en enhebrar todas las ranuras del bloque, y conviene hacerla hacia atrás para que la lista quede en orden ascendente de direcciones: así, un patrón de reservas consecutivas al arrancar devuelve memoria contigua y el recorrido posterior es amable con la caché.

void pool_init(Pool *p, void *mem, size_t n, size_t tam_ranura) {
    p->bloque = mem;  p->tam_ranura = tam_ranura;  p->libres = nullptr;
    for (size_t i = n; i-- > 0; ) {                 // hacia atras: direcciones ascendentes
        Ranura *r = (Ranura *)((unsigned char *)mem + i * tam_ranura);
        r->siguiente = p->libres;
        p->libres = r;
    }
}

Tamaño de ranura, alineación y crecimiento

Tres condiciones deben cumplirse para que el juego de manos sea legítimo, y saltarse cualquiera produce fallos que aparecen tarde y en máquinas ajenas.

La ranura debe medir al menos lo que un puntero, o el enlace no cabe donde se pretende escribirlo. Debe estar alineada al menos como el tipo que alojará y como el propio puntero, porque una dirección desalineada es comportamiento indefinido aunque el procesador la tolere. Y su tamaño debe ser múltiplo de esa alineación, para que la ranura siguiente herede la propiedad. Todo ello es comprobable en compilación.

#define POOL_TAM_RANURA(T) \
    (sizeof(T) < sizeof(void *) ? sizeof(void *) : sizeof(T))

static_assert(alignof(Nodo) <= alignof(max_align_t));
static_assert(POOL_TAM_RANURA(Nodo) % alignof(Nodo) == 0);

Cuando el bloque se agota hay una respuesta correcta y una tentadora pero errónea. La correcta es pedir otro bloque y enhebrar sus ranuras en la lista libre existente, encadenando los bloques para poder devolverlos al final. Los punteros ya entregados no se mueven jamás, que es precisamente la propiedad por la que se elige un pool. La errónea es llamar a realloc sobre el bloque: si el sistema lo reubica, todos los punteros vivos y todos los enlaces de la lista libre quedan colgantes a la vez, con una corrupción silenciosa y prácticamente indepurable.

El tamaño de los bloques sucesivos también es una decisión con consecuencias medibles. Duplicarlo en cada crecimiento reduce el número de llamadas al sistema a un logaritmo, pero puede reservar el doble de lo necesario justo antes de que el programa deje de crecer; mantenerlo constante hace el consumo predecible, que es lo que quieres si alguien tiene que auditarlo. Un detalle fácil de pasar por alto: conviene que el bloque mida un múltiplo del tamaño de página y que la cabecera de encadenamiento no descuadre la alineación de la primera ranura, o cada bloque nuevo desalineará todo lo que contenga.

Hay una consecuencia de rendimiento que la teoría suele omitir. Un pool no garantiza localidad por sí mismo: la garantiza al principio, cuando la lista libre está en orden de direcciones, y la va perdiendo a medida que un patrón desordenado de liberaciones enhebra la lista saltando de un extremo a otro del bloque. Tras horas de uso, recorrer objetos obtenidos consecutivamente puede tocar páginas dispersas. Si el recorrido importa más que la reserva, la respuesta no es un pool sino un array denso con reubicación e índices, que sacrifica la estabilidad de los punteros para conservar la contigüidad.

Cuando los tamaños no son uniformes pero sí acotados, la generalización natural es un conjunto de pools segregados por clase de tamaño: dieciséis, treinta y dos, sesenta y cuatro bytes, y así sucesivamente. Es la arquitectura del slab allocator que Jeff Bonwick describió en 1994 para SunOS, del asignador SLUB del núcleo de Linux y, en el fondo, de los asignadores modernos de propósito general como tcmalloc o mimalloc, que son colecciones de pools por clase de tamaño con una vía lenta para lo que no encaja.

flowchart LR
L[Cabeza de la lista libre] --> R1[Ranura 3]
R1 --> R2[Ranura 7]
R2 --> R3[Ranura 1]
R3 --> N[Nulo]
A[pool alloc devuelve la cabeza] --> L
F[pool free reinserta al frente] --> L
style N fill:#f38ba8,color:#11111b

Patologías: aliasing, doble liberación y concurrencia

El truco de escribir un puntero encima de un objeto muerto roza una regla delicada del lenguaje. El aliasing estricto dice que un objeto no puede leerse a través de un tipo incompatible con su tipo efectivo, y aquí la misma memoria es unas veces Nodo y otras Ranura. La forma defendible ante un compilador agresivo es asignar el tipo efectivo con cada escritura —escribir el enlace mediante un lvalue de tipo Ranura establece ese tipo efectivo para la memoria asignada dinámicamente— o, si quieres máxima portabilidad, transportar el enlace con memcpy, que el compilador reduce a un movimiento en cualquier nivel de optimización.

void pool_free_portable(Pool *p, void *obj) {
    memcpy(obj, &p->libres, sizeof p->libres);   // sin lvalue de tipo ajeno
    p->libres = obj;
}

La segunda patología es estructural y no la detecta ningún sanitizador de serie. Liberar dos veces la misma ranura inserta la misma dirección dos veces en la lista libre, y a partir de ahí el pool entregará el mismo objeto a dos propietarios distintos que se sobrescribirán mutuamente; si el doble free es consecutivo, la lista queda con un ciclo de longitud uno y el pool empieza a devolver eternamente la misma ranura. Las defensas útiles son baratas: en compilaciones de depuración, rellenar la ranura con un patrón reconocible al liberarla y comprobarlo al reservar; o marcar con un bit de estado por ranura en un mapa aparte.

La defensa fuerte no es una comprobación sino un cambio de interfaz: sustituir el puntero por un handle de índice y generación. El índice localiza la ranura, la generación se incrementa en cada liberación, y resolver un handle rancio devuelve nulo de forma determinista en lugar de un puntero a un objeto ajeno. Con ello el uso tras liberar deja de ser comportamiento indefinido y pasa a ser un error detectable y tratable, además de reducir la referencia a treinta y dos o cuarenta y ocho bits serializables.

Conviene añadir una defensa más, porque los sanitizadores tampoco ven aquí lo que verían con malloc. Para AddressSanitizer, el pool entero es un bloque legítimo, así que un desbordamiento de una ranura sobre la siguiente es una escritura perfectamente válida y un uso tras liberar es un acceso a memoria viva. La solución es la misma que en las arenas: envenenar la ranura al devolverla a la lista y desenvenenarla al entregarla, dejando fuera los bytes del enlace.

void pool_free_asan(Pool *p, void *obj) {
    pool_free(p, obj);
    ASAN_POISON_MEMORY_REGION((unsigned char *)obj + sizeof(Ranura),
                              p->tam_ranura - sizeof(Ranura));
}

La tercera patología llega con los hilos. Una lista libre compartida es un punto de contención brutal, porque cada reserva y cada liberación escriben en la misma línea de caché y la arrancan de un núcleo a otro. Envolverla en un mutex funciona pero destruye la escalabilidad; hacerla sin bloqueos con comparación e intercambio introduce el problema ABA, en el que un hilo lee la cabeza, se duerme, y al despertar la dirección coincide pero la lista ha cambiado por debajo, lo que obliga a contadores de versión o a punteros etiquetados. La solución habitual en la práctica evita ambos caminos: un pool por hilo, con almacenamiento thread_local, y un mecanismo lento y poco frecuente para devolver bloques enteros al sistema. Es, otra vez, resolver un problema difícil suprimiendo la compartición que lo causaba.