Patrones embebidos comunes: pool de memoria

Esta es la segunda parte de la serie donde vuelvo a explorar los patrones embebidos más comunes. Esta vez le toca al pool de memoria (memory pool). Este patrón se usa a menudo como alternativa a malloc() y free().

El código fuente completo y probado vive en el repositorio complementario: ileanmjr88/tetzontli. Cada patrón de esta serie es su propio módulo con una suite completa de pruebas en GoogleTest, así que puedes clonarlo y ejecutar las pruebas tú mismo.

Concepto básico

Empecemos con una comparación rápida contra el búfer circular. Ambos patrones sirven para guardar datos, pero difieren en el punto de vista desde el cual lo hacen. Al búfer circular lo llamamos contenedor. Cada elemento que se inserta en la estructura de datos es homogéneo y uniforme, y el búfer es dueño del orden de esos datos: se empuja por un lado y se saca por el otro, siguiendo FIFO. El búfer sabe qué hay dentro, al menos en cuanto a tamaño y secuencia.

El pool de memoria toma el punto de vista opuesto. No es un contenedor, es gestión de memoria propia. No conoce la estructura de los datos que se guardan, no le importa qué contienen, y no lleva registro de la secuencia. Uno pide un bloque, el pool revisa si hay alguno disponible, y si lo hay, devuelve un puntero a ese bloque. Desde el punto de vista del pool solo existen bloques ocupados o libres, sin referencia a su estructura ni al orden en que se entregaron.

Llegados a este punto, la pregunta obvia es qué es un pool de memoria en los términos más simples. Es un búfer de bloques de memoria del mismo tamaño, normalmente implementado como un arreglo, así que tenemos un trozo o pool de memoria del cual tomar. Nuestro init determina el tamaño de los bloques e inicializa la estructura administradora que lleva registro de dónde está el siguiente bloque disponible.

Un repaso rápido a malloc() y free()

Antes de entrar al pool de memoria en sí, vale la pena dar un paso atrás y recordar qué hacen realmente malloc() y free(). Es importante porque vamos a implementar una funcionalidad parecida. La diferencia es que nosotros reservamos por adelantado un búfer de tamaño fijo, normalmente un arreglo estático, mientras que estas funciones reservan y liberan memoria del heap de forma dinámica.

malloc() le pide al asignador del heap un trozo de memoria del tamaño del elemento que se quiere guardar. Si la reserva tiene éxito, es decir, si el asignador encontró espacio, devuelve un puntero. Si no logra encontrar espacio devuelve NULL, indicando el fallo. El asignador del heap gestiona esto llevando su propio registro interno de los trozos libres y usados. Cada vez que usamos malloc() lleva registro de cuánto usamos, y lo mismo con free(): cada vez que liberamos memoria la marca como disponible. free() hace lo contrario de malloc(): se llama con el puntero que queremos devolverle al asignador del heap, este marca ese trozo como libre, y sigue adelante.

Estas dos funciones para reservar y liberar memoria dinámicamente funcionan muy bien en computadoras modernas y en granjas de servidores, donde hay grandes cantidades de memoria y un espacio de direcciones amplio. Si un malloc() tarda un microsegundo más en encontrar un trozo de memoria no pasa nada. Los sistemas embebidos no pueden hacer esas mismas suposiciones, y ahí es donde empiezan a aparecer las grietas:

• Fragmentación : a medida que reservamos y liberamos trozos de tamaños mezclados, la memoria libre que va quedando deja de ser contigua. Con el tiempo una petición falla aunque en total haya bytes libres de sobra, solo que no hay suficientes juntos. El fallo llega tarde, es intermitente y no se reproduce en el banco de pruebas.
• Tiempos no deterministas : no todo sistema embebido necesita tiempos deterministas, pero para los que sí, malloc() es un problema. El asignador busca un trozo que quepa, así que cuánto tarda depende del estado del heap. Eso es difícil de aceptar en un bucle con plazos estrictos, e imposible de presupuestar.
• Fallo tardío : uno se entera de que se quedó sin memoria justo en el momento en que necesita memoria, que suele ser el momento en que menos puede hacer al respecto. No hay respuesta en tiempo de arranque ni en tiempo de enlazado a la pregunta «¿esto va a caber?».

Llevar el registro de los bloques disponibles

Que no usemos malloc() ni free() también significa que no usamos el administrador del heap, que llevaba su propio registro de qué trozos estaban libres y cuáles entregados. Nuestra implementación tiene que hacer esa contabilidad por su cuenta. En realidad solo hay dos cosas que necesita saber: si hay algún bloque disponible, y si lo hay, dónde está.

Antes de entrar en la implementación que se usa en el repositorio tetzontli, exploremos brevemente dos enfoques comunes para esta contabilidad. El primero es el mapa de bits (bitmap), donde cada bit de un entero indica si un bloque está en uso o libre. La cantidad de bloques determina el tipo de entero que se usa. La alternativa es el método de la lista de libres (free list), que enhebra los bloques disponibles en una lista enlazada y mantiene un puntero apuntando al siguiente bloque disponible. Al liberar, el bloque vuelve al frente de ese puntero. Hay una ventaja clara en el método de la lista de libres: nunca tiene que buscar. Tomar un bloque significa quedarse con aquello a lo que apunta el puntero de seguimiento, y devolver uno significa ponerlo al frente. Ambas son una sola actualización de puntero, sin importar qué tan lleno esté el pool. El mapa de bits tiene que recorrer buscando un bit libre, y cuánto tarda depende de cuántos bloques ya estén en uso. Eso sí, el mapa de bits tiene una ventaja a la que estamos renunciando: como registra el estado de cada bloque, puede distinguir una doble liberación de una legítima. La lista de libres no puede, y volveremos a lo que eso nos cuesta.

La implementación de tetzontli usa el enfoque de lista de libres intrusiva. Es una variación común donde cada bloque libre sabe por sí mismo dónde está el siguiente trozo de memoria disponible. La razón de este enfoque es que no hace falta un mapa de bits para llevar registro de los bloques disponibles, ya que nuestro puntero next ya sabe cuál es el siguiente bloque libre. También un recordatorio: como no reservamos memoria dinámicamente, usamos un arreglo como contenedor para crear el pool de memoria. Eso facilita el recorrido después del init. Una vez que empezamos a reservar y liberar, queremos que los bloques liberados más recientemente sean los primeros en entregarse, manteniéndolo como una pila, lo cual es más amigable con caché.

Implementación

Estructura del pool de memoria

Igual que en el búfer circular, vamos a crear un struct. Es una forma simple de mantener todos los parámetros juntos y accesibles desde un solo puntero.

// modules/memory_pool/memory_pool.h
typedef struct {
  uint8_t *base;
  size_t block_size;
  size_t capacity;
  size_t used;
  size_t high_water;
  void *free_head;
} memory_pool_t;

• uint8_t *base: la dirección del bloque 0, y el ancla desde la cual se mide todo el pool. Cada bloque vive en base + i * block_size. Es tentador leer esto como el primer byte del búfer que se le entrega al pool, y la mayoría de las veces eso es exactamente lo que es, pero los dos pueden separarse, por una razón que veremos en memory_pool_init().
• size_t block_size: esto es lo que solemos llamar el stride. Define el tamaño de cada bloque de memoria y qué tan separados están entre sí.
• size_t capacity: la cantidad de bloques del pool. Se fija en memory_pool_init() y nunca cambia. Cuántos están libres en un momento dado es capacity - used.
• size_t used: la cantidad de bloques entregados. memory_pool_alloc() lo incrementa y memory_pool_free() lo decrementa. Ojo: entregados, no en uso. El pool no tiene idea de qué se hace con un bloque, solo de si lo entregó y no lo ha recuperado.
• size_t high_water: el valor máximo que used ha alcanzado desde memory_pool_init(). Este es el número con el que se dimensiona el pool: ejecutar el sistema bajo la peor carga, leerlo de vuelta, y así se sabe cuántos bloques hacían falta realmente. Sobrevive deliberadamente a memory_pool_reset(). Devolver todos los bloques no cambia el hecho de que en algún momento se necesitaron todos esos a la vez, y borrar el pico tiraría a la basura la medición. Solo un memory_pool_init() nuevo lo reinicia.
• void *free_head: la cabeza de la lista de libres. El primer bloque disponible para entregar, o NULL cuando todos los bloques están fuera. La lista es intrusiva, es decir, sus enlaces viven dentro de los propios bloques libres en vez de en structs de nodo aparte. Cada bloque libre guarda un puntero al siguiente en sus primeros bytes. Eso es lo que hace que la lista de libres no cueste memoria extra, y es la razón por la que memory_pool_init() rechaza un block_size más chico que un puntero.

Función de redondeo hacia arriba

También vamos a aprovechar is_power_of_two() en este patrón, y además agregamos un método nuevo para redondear hacia arriba al siguiente múltiplo de a. Cubrimos is_power_of_two() en detalle en el post del búfer circular, así que no lo repetimos aquí. Rechaza el cero además de los números que no son potencia de dos, que es lo que impide que block_align = 0 llegue a round_up().

// modules/memory_pool/memory_pool.c
static size_t round_up(size_t x, size_t a) {
  return (x + (a - 1u)) & ~(a - 1u);
}

• (x + (a - 1u)): toma la variable x, el número que queremos redondear hacia arriba, y la variable a, la alineación a la que queremos redondearlo. Sumar a - 1 primero es lo que empuja cualquier valor que no esté ya en un límite más allá del siguiente.
• ~(a - 1u): toma el número por el que queremos alinear, le resta uno, y aplica un not a nivel de bits, lo cual nos da una máscara que limpia los bits bajos y deja intacto todo lo que está por encima.
• Tomar ambos lados y hacer el & a nivel de bits baja el valor de vuelta a un límite. Por sí solo eso redondearía hacia abajo. Sumar a - 1 primero es lo que lo convierte en un redondeo hacia arriba. Esto puede confundir a primera vista.

llamada: round_up(x = 12, a = 16);

- (x + (a - 1u)) = (12 + (16 - 1u)) = (12 + 15) = 27 = 0b00011011
- (a - 1u) = (16 - 1u) = 15

Siguiendo la evaluación del lado derecho del &
- ~(15) = ~(0b00001111) = 0b11110000

Ahora juntando ambos lados
- 0b00011011 & 0b11110000 = 0b00010000 = 16

Es decir, hay que redondear 12 hacia arriba hasta 16

Y cuando el valor ya está en un límite, nada se mueve:
- round_up(16, 16) = (16 + 15) & ~15
- 0b00011111 & 0b11110000 = 0b00010000 = 16

En el búfer circular, el truco de la máscara solo funcionaba porque la capacidad era potencia de dos. Aquí aplica la misma regla, salvo que recae sobre a, la alineación a la que redondeamos, y no sobre la capacidad. a tiene que ser potencia de dos, y por eso memory_pool_init() le aplica is_power_of_two() antes de hacer cualquier redondeo.

Ejemplo cuando a no es potencia de dos.

- round_up(12, 12) = (12 + 11) & ~11 = 23 & ~11
- 0b00010111 & ~0b00001011 = 0b00010111 & 0b11110100 = 0b00010100 = 20

Debería dar 12, ya que 12 ya es múltiplo de 12 y un redondeo correcto
lo dejaría igual. Falla porque 11 es 0b00001011, no una serie limpia
de unos, así que la máscara limpia los bits equivocados.
Por eso aquí se usa la potencia de dos, para poder optimizar round_up.

Funciones de lectura y escritura del siguiente

Este par de funciones son las que leen cuál es el siguiente bloque disponible y actualizan cuál pasa a serlo. Empecemos con read_next(): para cada reserva vamos a necesitar leer dónde está el siguiente bloque a entregar.

// modules/memory_pool/memory_pool.c
static void *read_next(const void *block) {
  void *const *slot = (void *const *)block;
  void *next;
  memcpy(&next, slot, sizeof next);
  return next;
}

Esta función toma el puntero block, que llega como const void *, y lo castea a void *const *. Ese cast se lee de derecha a izquierda: slot es un puntero a un puntero constante a void. El const aplica al puntero guardado dentro del bloque, no a slot en sí, y está ahí para que el cast no descarte silenciosamente el calificador que el parámetro ya traía. Creamos la variable void *next como contenedor al cual copiar. Hacemos una copia de memoria de sizeof next bytes desde el slot hacia next. Así es como devolvemos un puntero al siguiente bloque de datos disponible.

Vale la pena detenerse en el memcpy, porque la versión obvia es una sola línea, return *(void **)block;. El problema es que esos bytes viven dentro de un arreglo de uint8_t, así que leerlos a través de un void** significa acceder a un objeto mediante un puntero de otro tipo, que es justo lo que prohíben las reglas de aliasing. El compilador tiene permiso de asumir que no hicimos eso. memcpy es la manera sancionada de decir «copia estos bytes tal cual sin afirmar nada sobre tipos», y no cuesta nada en cualquier nivel de optimización por encima de -O0: todo compilador reconoce un memcpy del tamaño de un puntero y emite una sola carga o escritura. En una compilación de depuración se queda como una llamada real, lo cual conviene saber pero no amerita cambiar el código.

Sigue write_next():

// modules/memory_pool/memory_pool.c
static void write_next(void *block, void *next) {
  void **slot = (void**)block;
  memcpy(slot, &next, sizeof next);
}

Esta función es el espejo de read_next(). La diferencia es que recibimos void *block y declaramos slot como void **, asignándole el cast de block, lo cual le dice al compilador que trate esos primeros bytes como un lugar donde vive un puntero. Después copiamos sizeof next bytes desde &next, la dirección de nuestra variable local, hacia el slot. Lo que queda en el bloque es el valor del puntero mismo. Ninguna de estas dos funciones mira nunca block_size, solo tocan los primeros sizeof(void *) bytes, y por eso la lista de libres cuesta lo mismo sin importar qué tan grandes sean los bloques.

Función de reinicio (reset)

Antes de llegar a la función init, conviene hablar de cómo reiniciamos el pool de memoria. Esta hace el trabajo de reenlazar los bloques de memoria en orden secuencial, lo cual la vuelve práctica para reutilizarla dentro de init.

// modules/memory_pool/memory_pool.c
void memory_pool_reset(memory_pool_t *mp) {
  if (mp == NULL) {
    return;
  }

  mp->free_head = NULL;
  for (size_t i = mp->capacity; i-- > 0;) {
    uint8_t *blk = mp->base + i * mp->block_size;
    write_next(blk, mp->free_head);
    mp->free_head = blk;
  }
  mp->used = 0u;
}

Empezamos con una verificación rápida de que no le pasamos un puntero NULL a la función. Sin ella, la siguiente línea, mp->free_head = NULL, dereferenciaría ese handle nulo. En una computadora de escritorio eso es un fallo de segmentación. En la mayoría de los microcontroladores no hay MMU que lo atrape, así que la dirección cero es memoria real, a menudo la tabla de vectores, y la escritura tiene éxito en silencio y corrompe algo. Si mp es una dirección de memoria real, ponemos mp->free_head = NULL para saber desde qué estado partimos antes de asignar el puntero siguiente en cada bloque.

Después iteramos con for (size_t i = mp->capacity; i-- > 0;). El decremento vive dentro de la comparación, así que la verificación va primero y el decremento después, lo que significa que el cuerpo ve desde capacity - 1 hasta 0, y el bucle termina después de ejecutar el 0. La versión obvia, for (size_t i = capacity - 1; i >= 0; i--), nunca termina. size_t es sin signo, así que i >= 0 siempre es verdadero, y decrementar 0 da la vuelta hasta SIZE_MAX en lugar de volverse negativo. Este es el mismo desbordamiento sin signo en el que nos apoyamos con el count del búfer circular, solo que aquí trabaja en nuestra contra.

La dirección importa por una segunda razón. Cada pasada escribe la cabeza actual dentro de un bloque y luego hace de ese bloque la nueva cabeza, así que recorrer el arreglo hacia atrás produce una lista que sale hacia adelante. Después de un reinicio, el primer memory_pool_alloc() devuelve el bloque 0, el siguiente devuelve el 1, y así en orden de direcciones. Si se construye la lista al revés el pool funciona igual, solo que entrega direcciones descendentes, lo cual es más difícil de leer cuando uno está mirando valores de punteros en un depurador.

memory_pool_reset() reconstruye la lista completa sin preguntar quién tiene qué, así que invalida todos los punteros pendientes. used vuelve a cero, mientras que high_water deliberadamente no.

Función de inicialización

La función de inicialización es nuestro punto de entrada para empezar a usar el patrón. Acepta como parámetros: memory_pool_t *mp, void *storage, size_t storage_size, size_t block_size, size_t block_align.

// modules/memory_pool/memory_pool.c
bool memory_pool_init(memory_pool_t *mp, void *storage, size_t storage_size, size_t block_size, size_t block_align) {
  if (mp == NULL || storage == NULL || !is_power_of_two(block_align) || block_size < sizeof(void *)) {
    return false;
  }

  if (block_align < _Alignof(void *)) {
    block_align = _Alignof(void *);
  }

  size_t stride = round_up(block_size, block_align);
  if (stride < block_size) {
    return false;
  }

  uintptr_t addr = (uintptr_t)storage;
  uintptr_t aligned = (uintptr_t)round_up((size_t)addr, block_align);
  uint8_t *base = (uint8_t *)aligned;

  size_t offset = (size_t)(base - (uint8_t *)storage);
  if (offset >= storage_size) {
    return false;
  }

  size_t usable = storage_size - offset;
  size_t capacity = usable / stride;
  if (capacity == 0u) {
    return false;
  }

  mp->base = base;
  mp->block_size = stride;
  mp->capacity = capacity;
  mp->used = 0u;
  mp->high_water = 0u;
  memory_pool_reset(mp);
  return true;
}

Lo primero al pasar o manejar punteros es asegurarse de que no sean NULL. Un puntero nulo significa que estaríamos escribiendo en la dirección de memoria cero. Como ya dijimos, en una computadora eso es un fallo de segmentación, pero aquí podríamos escribir en la dirección cero y corromper una dirección no intencionada. La verificación también comprueba explícitamente que block_align sea potencia de dos, ya que round_up se llama dos veces más abajo y solo funciona bajo esa garantía. La última verificación es block_size < sizeof(void *). Cualquier bloque que entreguemos tiene que ser lo bastante grande para guardar un enlace de la lista de libres mientras está libre, así que un bloque más chico que un puntero derramaría su enlace sobre el bloque de al lado.

• Ajuste de alineación: block_align se sube a _Alignof(void *) si se pide menos. Está permitido pedir alineación de 1 byte, pero la lista de libres guarda un puntero dentro de cada bloque libre, así que el pool entrega en silencio alineación de puntero en su lugar. Misma razón que la guarda de block_size, desde el otro lado. Conviene explicitar lo que se desprende de esto: como base está alineado y el stride es múltiplo de block_align, todos los bloques del pool quedan alineados, no solo el primero. Esa es la garantía en la que uno se apoya al meter un struct en un bloque, así que hay que pasar _Alignof(T) para un pool de T. El ajuste por sí solo únicamente promete alineación de puntero.
• Guarda de desbordamiento: if (stride < block_size) parece inalcanzable, ya que redondear hacia arriba no puede hacer un número más chico. Lo que atrapa es la vuelta al inicio: round_up suma a - 1 antes de enmascarar, y si block_size está cerca de SIZE_MAX esa suma da la vuelta. Es el desbordamiento sin signo mordiéndonos otra vez, esta vez atrapado a propósito.
• Corrimiento de la base: el búfer de quien llama puede no empezar en una dirección alineada, así que base se redondea hacia arriba y los bytes iniciales se pierden. Eso es offset, y por eso base y storage pueden diferir.
• Cálculo de la capacidad: usable / stride, descartando el resto. Entre el corrimiento y el truncamiento, la capacidad suele ser menor que storage_size / block_size, y por eso existe memory_pool_capacity() en vez de que quien llama la calcule. Si uno alinea su propio almacenamiento, con alignas en el arreglo puesto al menos tan grande como el block_align que pasa, el corrimiento no cuesta nada. Si se deja al azar, se puede perder un bloque en silencio.

Funciones de reserva y liberación

Ahora que inicializamos el pool de memoria podemos empezar a usarlo. A memory_pool_alloc() hay que pasarle el parámetro memory_pool_t *mp:

// modules/memory_pool/memory_pool.c
void *memory_pool_alloc(memory_pool_t *mp) {
  if (mp == NULL || mp->free_head == NULL) {
    return NULL;
  }

  void *p = mp->free_head;
  mp->free_head = read_next(p);
  mp->used++;
  if (mp->used > mp->high_water) {
    mp->high_water = mp->used;
  }
  return p;
}

Hacemos nuestra verificación estándar de que mp no sea NULL, y junto a ella verificamos mp->free_head. Esa segunda es la forma en que un pool agotado se anuncia: que la lista de libres esté vacía es que la cabeza sea NULL, así que no hace falta un helper is_empty aparte como sí lo necesitaba el búfer circular. Devolver NULL aquí también coincide con malloc(), así que quien ya maneja una reserva fallida no tiene que aprender una convención nueva. Si ambas verificaciones pasan, creamos un puntero nuevo p y lo apuntamos a mp->free_head. Ese es el bloque que estamos por devolverle a quien llama, y antes de soltarlo llamamos a read_next(p) para sacar el enlace de sus primeros bytes, que es lo que pasa a ser la nueva cabeza. Lo último que hacemos es contabilidad: mp->used++ registra que hay un bloque más entregado, y si eso empuja used por encima de mp->high_water subimos el pico con él. Esa comparación es el único lugar donde high_water cambia.

Sigue memory_pool_free():

// modules/memory_pool/memory_pool.c
bool memory_pool_free(memory_pool_t *mp, void *block) {
  if (!memory_pool_owns(mp, block)) {
    return false;
  }
  if (mp->used == 0u) {
    return false;
  }

  write_next(block, mp->free_head);
  mp->free_head = block;
  mp->used--;
  return true;
}

Devolver un bloque es la imagen espejo. La primera verificación le pasa el puntero a memory_pool_owns(), tema de la siguiente sección, que responde si esto es realmente el inicio de un bloque de este pool. La segunda, mp->used == 0u, rechaza una liberación en un pool que no tiene nada pendiente. Ambas se ejecutan antes de escribir nada, así que una liberación rechazada deja el pool completamente intacto, lista de libres incluida. El orden de esas dos tampoco es intercambiable, ya que mp->used dereferencia mp y solo es seguro porque memory_pool_owns() ya rechazó un pool nulo. Si se invierten para fallar primero en la verificación más barata, lo que se escribió es una dereferencia nula.

Después empujamos. write_next(block, mp->free_head) escribe la cabeza actual dentro del bloque devuelto, mp->free_head = block hace de ese bloque la nueva cabeza, y mp->used-- baja la cuenta. Este es el comportamiento de pila del que hablábamos antes: el bloque que se acaba de devolver es el que va a entregar el siguiente memory_pool_alloc().

Hay un caso que estas verificaciones no pueden atrapar: liberar el mismo bloque dos veces. Volveremos a eso después de la implementación.

El pool es dueño de la dirección de memoria

// modules/memory_pool/memory_pool.c
bool memory_pool_owns(const memory_pool_t *mp, const void *p) {
  if (mp == NULL || p == NULL) {
    return false;
  }

  uintptr_t addr = (uintptr_t)p;
  uintptr_t base = (uintptr_t)mp->base;
  uintptr_t end = base + ((uintptr_t)mp->capacity * (uintptr_t)mp->block_size);

  if (addr < base || addr >= end){
    return false;
  }
  return (addr - base) % (uintptr_t)mp->block_size == 0u;
}

Esta es la validación en la que se apoya memory_pool_free(), y hace dos preguntas. La primera es si el puntero está dentro de la zona del pool siquiera, comparándolo contra base y end.

La segunda es la interesante: (addr - base) % mp->block_size == 0u verifica que el puntero esté exactamente en un límite de bloque. Un puntero al medio de un bloque pasa la prueba de rango pero no es un bloque, y liberarlo insertaría un nodo falso en la lista de libres a un desplazamiento, así que la siguiente reserva entregaría un bloque que se solapa con su vecino. Esta operación módulo es la única división de todo el módulo, y es el mismo costo que evitamos en el búfer circular. Hacer que el stride sea potencia de dos la vuelve a convertir en una máscara.

Función de capacidad

Conocer la capacidad es importante porque a partir de ella podemos identificar cuánto del pool de memoria tenemos para entregar.

// modules/memory_pool/memory_pool.c
size_t memory_pool_capacity(const memory_pool_t *mp) {
  return (mp == NULL) ? 0u : mp->capacity;
}

Hacemos nuestra verificación de NULL sobre mp. Si es nulo devolvemos 0u, de lo contrario devolvemos la capacidad derivada allá en memory_pool_init().

Funciones auxiliares

Estas son las funciones para acceder a los miembros de memory_pool_t sin modificarlos. Empezamos con memory_pool_used():

// modules/memory_pool/memory_pool.c
size_t memory_pool_used(const memory_pool_t *mp) {
  return (mp == NULL) ? 0u : mp->used;
}

Aquí solo verificamos que el mp pasado como argumento no sea NULL, y si no lo es devolvemos el campo que pedimos, en este caso mp->used.

// modules/memory_pool/memory_pool.c
size_t memory_pool_available(const memory_pool_t *mp) {
  return (mp == NULL) ? 0u : mp->capacity - mp->used;
}

size_t memory_pool_high_water(const memory_pool_t *mp) {
  return (mp == NULL) ? 0u : mp->high_water;
}

Aquí está el resto de las funciones auxiliares, siguiendo la misma verificación de NULL y devolviendo el valor que pedimos. Nótese que memory_pool_available() calcula capacity - used en lugar de recorrer la lista de libres para contar lo que queda, que es la misma respuesta sin el recorrido.

Ejemplo de uso

Ahora que explicamos la implementación completa, veamos cómo vamos a usar el patrón.

typedef struct {
  uint32_t timestamp;
  int16_t value;
  uint8_t sensor_id;
} sample_t;

static alignas(void *) uint8_t sample_storage[16 * sizeof(sample_t)];
static memory_pool_t sample_pool;
static sample_t *current;

bool sensor_init(void) {
  return memory_pool_init(&sample_pool, sample_storage, sizeof sample_storage,
                          sizeof(sample_t), _Alignof(sample_t));
}

bool sensor_take_reading(uint8_t sensor_id) {
  current = memory_pool_alloc(&sample_pool);
  if (current == NULL) {
    return false;
  }

  current->timestamp = now();
  current->value = read_adc(sensor_id);
  current->sensor_id = sensor_id;
  return true;
}

void sensor_flush(void) {
  if (current == NULL) {
    return;
  }

  transmit(current);
  memory_pool_free(&sample_pool, current);
  current = NULL;
}

Este ejemplo muestra que vamos a usar el pool de memoria para guardar sample_t, que está compuesto por timestamp, value y sensor_id. Nótese que el bloque se reserva en una función y se libera en otra. Ese es el punto del pool: la memoria sobrevive a la llamada que la pidió, que es lo que permite que una lectura se quede ahí hasta que algo más esté listo para ocuparse de ella. Un solo espacio mantiene corto el ejemplo; un llamador real tiene varios a la vez.

Ahora el alignas(void *) sobre sample_storage. A init le pasamos _Alignof(sample_t), pero init lo sube a _Alignof(void *), porque todo bloque libre tiene que poder guardar un puntero. El almacenamiento tiene que satisfacer al mayor de los dos, y aquí ese es void *: en un host de 64 bits son 8 contra los 4 de sample_t, y en un objetivo de 32 bits los dos son iguales, así que alinear al puntero cubre ambos casos. Si uno se equivoca, base se corre hacia adelante y se pierde un bloque en silencio. Nótese que declaramos sample_storage como uint8_t, así que el arreglo son bytes crudos y podemos dimensionarlo multiplicando la cantidad de bloques por sizeof(sample_t). Ojo que alignas necesita <stdalign.h> en C11, y el fragmento omite los includes.

Nótese también que el pool no tiene idea de a qué sensor pertenece un bloque. sensor_id es un campo que pusimos nosotros en el struct, no algo que el pool registre. Lo único que supo siempre fue el tamaño de bloque y la alineación que le entregamos en init.

Nótese que alloc, free, y la forma en que usamos la memoria entre medio tienen la misma forma que malloc() y free(). Pedir memoria, verificar NULL, usarla, devolverla. Eso es deliberado: el código escrito contra el heap se porta cambiando dos puntos de llamada. Dos diferencias que conviene conocer: memory_pool_free() devuelve un bool en lugar de nada, y liberar el mismo bloque dos veces no se comporta como lo haría el asignador del heap. Vamos a eso ahora.

Caso límite: doble liberación

Allá en memory_pool_free() dijimos que había un caso que las verificaciones no pueden atrapar. Liberar en un pool vacío lo rechaza mp->used == 0u, y un puntero que no es el inicio de un bloque lo rechaza memory_pool_owns(). Pero liberar un bloque que ya está en la lista de libres pasa ambas. Es un inicio de bloque legítimo, así que owns dice que sí, y hay otros bloques pendientes, así que used no es cero.

Así que el empuje se ejecuta. Escribimos free_head dentro del bloque y luego hacemos de ese bloque la nueva cabeza. Si ese bloque ya era la cabeza, ahora se apunta a sí mismo.

Antes:
  free_head -> [B] -> [C] -> NULL

memory_pool_free(mp, B) por segunda vez:
  write_next(B, free_head) el next de B ahora apunta a B
  free_head = B

Después:
  free_head -> [B] -> [B] -> [B] -> ...

  alloc() devuelve B
  alloc() devuelve B otra vez, a otro llamador

Nada reporta esto. memory_pool_free() devuelve true, used se ve plausible, y toda consulta dice que el pool está sano. Uno lo encuentra después, en el código que tuvo la mala suerte de ser el segundo dueño del bloque.

Hay formas de atraparlo, y ambas cuestan algo por lo cual elegimos este patrón. Podríamos recorrer la lista de libres en cada liberación y rechazar un bloque que ya esté en ella, lo cual es correcto y convierte una liberación de tiempo constante en un recorrido. Podríamos mantener un mapa de bits aparte con los bloques reservados, lo cual cuesta memoria y renuncia a la propiedad de cero sobrecarga que motivó la lista intrusiva en primer lugar. Para una base de código de firmware pequeña, donde los puntos de reserva son pocos y revisables, documentarlo es una decisión defendible, y la limitación está escrita en el header justo al lado de la función que no puede atraparla. Para una base de código más grande valdría la pena pagar una verificación en la compilación de depuración.

Cierre

Eso es un pool de memoria completo. No hace reserva dinámica, entrega bloques y los recupera en tiempo constante sin búsquedas, no lleva ni un byte de sobrecarga por bloque, no puede fragmentarse por construcción, y después dice cuánto de él hacía falta realmente.

Los sacrificios, todos deliberados:

• Un solo tamaño por pool. Cuatro tipos de objeto significan cuatro pools. Esto es lo que compra la ausencia de fragmentación, y hace que el pool sea mala opción para datos de tamaño genuinamente variable.
• No es thread-safe ni ISR-safe. A diferencia del búfer circular, aquí no hay un camino sin bloqueos. Toda llamada que muta toca free_head, y no hay forma de repartir eso entre dos contextos como sí se reparten head y tail. Un pool compartido necesita una sección crítica alrededor de cada llamada que muta, que es también la razón por la que no hay ningún volatile en memory_pool_t.
• Los bloques no se ponen en cero. Estas son semánticas de malloc, no de calloc. Un bloque recién entregado tiene un puntero viejo de la lista de libres en sus primeros bytes y lo que haya dejado el dueño anterior en el resto.
• La doble liberación solo es parcialmente detectable. Cubierto arriba, y la limitación más importante del módulo.
• La capacidad se deriva, no se da. El redondeo del stride, el corrimiento por alineación y el resto de la cola le comen espacio. Hay que leerla de vuelta con memory_pool_capacity().

Dos patrones y ya empezaron a apoyarse uno en el otro. El búfer circular nos dio almacenamiento fijo para bytes, el pool nos da almacenamiento fijo para objetos, y la cola de eventos, más adelante en la serie, va a querer los dos: un anillo de punteros a bloques entregados por un pool. Así se consigue una cola de structs sin una sola llamada a malloc.

Lo que sigue en la serie es la máquina de estados. El búfer circular y el pool trataron con almacenamiento, bytes en uno y bloques en el otro, y a ninguno le importaba qué significaba nada de eso. La máquina de estados es donde empieza a significar algo.