Un malloc propio con lista libre

1. Qué vamos a construir

Lista libre es una estructura que enlaza los bloques disponibles para futuras peticiones. Al asignar, se retira o divide uno de esos bloques; al liberar, el bloque vuelve a la lista y puede fusionarse con huecos físicamente contiguos.

Reservaremos una sola región de 64 KiB con mmap. Al principio toda la capacidad administrada será un bloque libre. Las peticiones se resolverán dentro de esa región; si no hay un hueco suficiente, devolveremos NULL. No creceremos automáticamente ni moveremos el break que utiliza la biblioteca.

Los nombres propios permiten utilizar printf y otras funciones sin reemplazar el malloc de libc. No instalaremos el código como asignador global ni mediante LD_PRELOAD. Es una implementación didáctica para un único hilo, sin calloc ni realloc y con capacidad fija.

Solo se admiten punteros devueltos por mi_malloc que todavía estén vivos. No es un validador de punteros arbitrarios. Al destruir la región se pierden sus cabeceras y toda su capacidad, por lo que se rechaza esa operación si hay objetos activos.

2. La cabecera de cada bloque

Cada bloque comienza con una cabecera que el usuario no debe tocar. Después viene el espacio entregado a la aplicación:

inicio del bloque                         puntero entregado
        |                                         |
        v                                         v
        [ cabecera: tamaño, siguiente, libre ][ datos y posible relleno ]
        <---------------- tamaño total del bloque -------------------->

En este diseño, tam siempre incluye la cabecera. Guardar tamaños totales simplifica la fusión: unir dos bloques contiguos consiste en sumar sus tamaños. El espacio de la cabecera del segundo deja de ser metadato y pasa a formar parte del área reutilizable del bloque combinado.

El puntero que recibe la aplicación es inicio + H, donde H es el tamaño de la cabecera. Para un puntero válido, mi_free recupera la cabecera restando H bytes. Esa resta no debe hacerse sobre un puntero de libc, una variable local o una dirección interior del objeto.

3. Alineación y cálculo del tamaño

Un bloque debe poder contener tipos ordinarios de C con alineación fundamental, como double o long double. No basta con que el primer bloque esté alineado: la cabecera y todos los desplazamientos que generamos también deben conservar la alineación.

Usaremos una unión que contiene los campos y un max_align_t. Así, la cabecera tiene al menos la alineación de ese tipo y su tamaño es múltiplo de la alineación correspondiente. El código consulta A mediante _Alignof(max_align_t) y comprueba que la base del mapeo la cumple.

necesario = redondear_hacia_arriba(n + H, A)
redondear(x, A) = ((x + A - 1) / A) * A

Ejemplo: A = 16, H = 32, n = 50
n + H = 82
necesario = 96
capacidad para datos = 96 - 32 = 64
relleno dentro del bloque = 64 - 50 = 14 bytes

Los valores A = 16 y H = 32 son ilustrativos. La implementación no los fija. Antes de sumar n + H y el ajuste A - 1, comprueba que no se desborde size_t. Un desbordamiento podría convertir una petición enorme en una reserva pequeña.

La fórmula con división no exige escribir una máscara ni asumir manualmente un tamaño de alineación. Este asignador no promete atender tipos con alineación extendida superior a max_align_t; para eso haría falta una interfaz y una estrategia adicionales.

4. Lista libre y orden físico

Hay dos recorridos distintos. El orden físico sigue todos los bloques que particionan la región; el enlace libre salta únicamente entre los huecos. La cabecera conserva el tamaño de los ocupados para poder inspeccionar el mapa, pero esos bloques no se enlazan en la lista libre.

Orden físico: [ A ocupado ][ B libre ][ C ocupado ][ D libre ]
Lista libre:                 B ---------------------> D --> NULL

Mantendremos la lista libre ordenada por desplazamiento creciente dentro de la región. Cuando se libera un bloque, su posición de inserción permite encontrar el hueco libre anterior y el posterior. Sin embargo, ser vecinos en la lista no prueba contigüidad: entre B y D sigue existiendo C.

La contigüidad se verifica con una igualdad: offset(anterior) + anterior->tam == offset(siguiente). Todos los offsets pertenecen a un único mapeo. No se usan comparaciones de orden entre punteros de regiones independientes.

5. Buscar por primer ajuste

Calculado el tamaño total necesario, recorremos la lista y elegimos el primer hueco cuyo tamaño alcanza. Es el primer ajuste del bloque 3, aplicado ahora a bloques dentro de una región privada del asignador.

Bloque **enlace = &lista_libre;
while (*enlace != NULL && (*enlace)->info.tam < necesario)
    enlace = &(*enlace)->info.sig;

El puntero a puntero permite actualizar de la misma forma la cabeza de la lista o el enlace de un bloque anterior. Si se consume el candidato completo, *enlace pasa a su sucesor. Si se divide, pasa a la nueva cabecera que representa el resto.

Si no hay candidato, se devuelve NULL con ENOMEM. Puede ocurrir aunque la suma de bytes libres sea grande: se necesita un hueco contiguo con capacidad para los datos, su cabecera y el ajuste de alineación.

6. Dividir sin crear huecos inútiles

Un hueco de 256 bytes puede atender una petición total de 96. La nueva cabecera del resto se coloca 96 bytes después de la cabecera original, y ese resto mide 160 bytes:

Antes:   [ bloque libre de 256 bytes ]
Después: [ ocupado de 96 bytes ][ libre de 160 bytes ]
          cabecera original      cabecera nueva

256 = 96 + 160

Pero no conviene dividir si el resto no permite alojar una cabecera y un área útil mínima. Adoptaremos H + A como tamaño mínimo de un bloque libre nuevo: una cabecera y una unidad alineada de datos.

Si el sobrante es menor, se entrega el bloque completo. Por ejemplo, con H = 32 y A = 16, un resto de 32 bytes no basta. Esos bytes quedan como capacidad adicional del bloque ocupado. El usuario sigue teniendo derecho a utilizar solo la cantidad solicitada.

La condición se expresa sobre una resta segura: como ya sabemos que el bloque alcanza, tam - necesario no puede ser negativa. Comparamos ese resultado con H + A y evitamos sumar innecesariamente al tamaño de la petición.

7. Liberar y fusionar vecinos

Al liberar se recupera la cabecera, se marca el bloque libre y se inserta en el lugar que le corresponde por offset. Después se comprueban ambos lados:

1. Sucesor libre contiguo. Se suma su tamaño y se salta su enlace: la cabecera del sucesor deja de ser independiente.
2. Predecesor libre contiguo. Se suma el bloque resultante al anterior y se actualiza el enlace de ese anterior.
3. Vecino ocupado o separado. No se fusiona; una fusión nunca puede cruzar un bloque vivo.

Antes: [ libre 96 ][ ocupado 160 ][ libre 128 ]
free:             ^
Después: [ libre 384 ]

96 + 160 + 128 = 384

La fusión recupera como espacio útil las cabeceras que desaparecen dentro del bloque combinado. No desplaza los bloques ocupados ni invalida sus punteros. La región sigue reservada: todavía no se llama a munmap.

Como fusionamos inmediatamente y el estado anterior era válido, basta con mirar los vecinos de inserción: no debe haber ya una cadena de huecos libres contiguos sin fusionar. Esa propiedad es una de nuestras invariantes.

8. Invariantes del asignador

Una operación puede parecer correcta y aun así dejar roto el estado para la siguiente. Estas propiedades deben mantenerse después de cada asignación o liberación:

• Los bloques físicos no se superponen y sus tamaños totales suman la capacidad administrada.
• Cada comienzo y cada tamaño de bloque conserva la alineación A.
• Cada bloque libre aparece exactamente una vez en la lista, y ningún ocupado aparece allí.
• La lista está ordenada por offset y no contiene ciclos.
• No quedan dos bloques libres físicamente contiguos sin fusionar.
• El contador de bloques vivos coincide con el número de bloques ocupados.

La capacidad administrada es el tamaño del mapeo redondeado hacia abajo a un múltiplo de A. En un entorno habitual los 64 KiB ya cumplen esa condición. Conservar por separado el tamaño del mapeo permite desmapear correctamente aunque existiera una pequeña cola no administrada.

La base, el tamaño del mapeo y la lista son estado del asignador. No se guardan en variables que vivan dentro de un bloque del usuario. Aun así, un desbordamiento de un objeto puede corromper la cabecera siguiente: la correcta disciplina de acceso sigue siendo imprescindible.

9. Implementación completa en C

Guarda este bloque como lista_libre.c. Incluye la implementación y una demostración con comprobaciones que siguen activas aunque se compile con NDEBUG. La región obtenida por mmap no tiene tipo declarado; las cabeceras se escriben sobre ese almacenamiento alineado.

#define _DEFAULT_SOURCE
#include <assert.h>
#include <errno.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>

#define REGION_BYTES (64UL * 1024)

typedef union Bloque Bloque;
union Bloque {
    struct {
        size_t tam;       /* tamaño total: cabecera + área de datos */
        Bloque *sig;      /* solo enlaza bloques libres */
        int libre;
    } info;
    max_align_t alineacion;
};

static unsigned char *region;
static size_t capacidad;
static size_t vivos;
static Bloque *lista_libre;

static size_t offset(const Bloque *b)
{
    return (size_t) ((const unsigned char *) b - region);
}

int mi_init(void)
{
    if (region != NULL) { errno = EBUSY; return -1; }
    size_t a = _Alignof(max_align_t);
    void *p = mmap(NULL, REGION_BYTES, PROT_READ | PROT_WRITE,
                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (p == MAP_FAILED) return -1;
    size_t cap = (REGION_BYTES / a) * a;
    if ((uintptr_t) p % a != 0 || cap < sizeof(Bloque) + a) {
        munmap(p, REGION_BYTES);
        errno = EINVAL;
        return -1;
    }
    region = p;
    capacidad = cap;
    vivos = 0;
    lista_libre = (Bloque *) region;
    lista_libre->info.tam = capacidad;
    lista_libre->info.sig = NULL;
    lista_libre->info.libre = 1;
    return 0;
}

void *mi_malloc(size_t n)
{
    if (n == 0) return NULL;
    if (region == NULL) { errno = EINVAL; return NULL; }
    size_t a = _Alignof(max_align_t);
    size_t h = sizeof(Bloque);
    if (n > SIZE_MAX - h) { errno = ENOMEM; return NULL; }
    size_t necesario = n + h;
    if (necesario > SIZE_MAX - (a - 1)) {
        errno = ENOMEM; return NULL;
    }
    necesario = ((necesario + a - 1) / a) * a;

    Bloque **enlace = &lista_libre;
    while (*enlace != NULL && (*enlace)->info.tam < necesario)
        enlace = &(*enlace)->info.sig;
    if (*enlace == NULL) { errno = ENOMEM; return NULL; }

    Bloque *b = *enlace;
    size_t sobrante = b->info.tam - necesario;
    if (sobrante >= h + a) {
        Bloque *resto = (Bloque *) (region + offset(b) + necesario);
        resto->info.tam = sobrante;
        resto->info.sig = b->info.sig;
        resto->info.libre = 1;
        *enlace = resto;
        b->info.tam = necesario;
    } else {
        *enlace = b->info.sig;
    }
    b->info.sig = NULL;
    b->info.libre = 0;
    vivos++;
    return (unsigned char *) b + h;
}

void mi_free(void *p)
{
    if (p == NULL) return;
    /* Precondición: p es un bloque vivo de esta región. */
    Bloque *b = (Bloque *) ((unsigned char *) p - sizeof(Bloque));
    assert(region != NULL && !b->info.libre);
    Bloque *anterior = NULL;
    Bloque *siguiente = lista_libre;
    while (siguiente != NULL && offset(siguiente) < offset(b)) {
        anterior = siguiente;
        siguiente = siguiente->info.sig;
    }
    b->info.libre = 1;
    b->info.sig = siguiente;
    if (anterior != NULL)
        anterior->info.sig = b;
    else
        lista_libre = b;

    if (siguiente != NULL && offset(b) + b->info.tam == offset(siguiente)) {
        b->info.tam += siguiente->info.tam;
        b->info.sig = siguiente->info.sig;
    }
    if (anterior != NULL && offset(anterior) + anterior->info.tam == offset(b)) {
        anterior->info.tam += b->info.tam;
        anterior->info.sig = b->info.sig;
    }
    vivos--;
}

void mi_dump(void)
{
    printf("Capacidad %zu; cabecera %zu; alineación %zu; vivos %zu\n",
           capacidad, sizeof(Bloque), (size_t) _Alignof(max_align_t), vivos);
    if (region == NULL) { puts("Sin región."); return; }
    for (size_t pos = 0; pos < capacidad;) {
        Bloque *b = (Bloque *) (region + pos);
        printf("  offset %5zu: total %5zu; %s\n", pos, b->info.tam,
               b->info.libre ? "libre" : "ocupado");
        pos += b->info.tam;
    }
    printf("Lista libre:");
    for (Bloque *b = lista_libre; b != NULL; b = b->info.sig)
        printf(" %zu", offset(b));
    puts(" -> NULL");
}

int mi_destroy(void)
{
    if (region == NULL) return 0;
    if (vivos != 0) { errno = EBUSY; return -1; }
    if (munmap(region, REGION_BYTES) == -1) return -1;
    region = NULL;
    capacidad = 0;
    lista_libre = NULL;
    return 0;
}

#ifndef LISTA_SIN_MAIN
static void exigir(int condicion, const char *mensaje)
{
    if (!condicion) {
        fprintf(stderr, "Comprobación fallida: %s\n", mensaje);
        exit(EXIT_FAILURE);
    }
}

int main(void)
{
    if (mi_init() == -1) { perror("mi_init"); return 1; }
    exigir(mi_malloc(0) == NULL, "petición cero");
    exigir(mi_malloc(SIZE_MAX) == NULL, "rechazar desbordamiento");
    unsigned char *a = mi_malloc(64);
    unsigned char *b = mi_malloc(128);
    unsigned char *c = mi_malloc(64);
    exigir(a != NULL && b != NULL && c != NULL, "tres reservas");
    exigir((uintptr_t) a % _Alignof(max_align_t) == 0, "alineación");
    memset(a, 0xA1, 64);
    memset(c, 0xC3, 64);
    size_t lugar_b = (size_t) (b - region);
    puts("1. Tres bloques ocupados:");
    mi_dump();
    exigir(mi_destroy() == -1 && errno == EBUSY, "no destruir con objetos vivos");

    mi_free(b);
    b = NULL;
    puts("2. Hueco interior liberado:");
    mi_dump();
    unsigned char *d = mi_malloc(48);
    exigir(d != NULL, "reutilizar el hueco");
    exigir((size_t) (d - region) == lugar_b, "primer ajuste reutiliza B");
    memset(d, 0xD4, 48);
    for (size_t i = 0; i < 64; i++) {
        exigir(a[i] == 0xA1, "preservar A");
        exigir(c[i] == 0xC3, "preservar C");
    }
    puts("3. Hueco reutilizado para 48 bytes:");
    mi_dump();

    mi_free(d);
    d = NULL;
    mi_free(a);
    a = NULL;
    mi_free(c);
    c = NULL;
    mi_free(NULL);
    exigir(vivos == 0 && lista_libre == (Bloque *) region &&
           lista_libre->info.tam == capacidad && lista_libre->info.sig == NULL,
           "fusión completa de la región");
    puts("4. Todos liberados y fusionados:");
    mi_dump();
    if (mi_destroy() == -1) { perror("mi_destroy"); return 1; }
    puts("Comprobaciones correctas.");
    return 0;
}
#endif

La comprobación assert dentro de mi_free ayuda a detectar algunos usos incorrectos mientras la cabecera sigue siendo reconocible. No vuelve válida una doble liberación y no garantiza detectar punteros falsos ni una cabecera que ya se fusionó. Con NDEBUG esa comprobación desaparece, pero las precondiciones de la API siguen siendo obligatorias.

El bloque LISTA_SIN_MAIN permite excluir la demostración al compilar una prueba aparte. No es necesario definirlo para seguir este tema: el archivo se compila directamente.

10. Seguir la ejecución y las llamadas al sistema

$ gcc -std=c17 -Wall -Wextra -Wpedantic -O2 lista_libre.c -o lista_libre
$ ./lista_libre
1. Tres bloques ocupados:
Capacidad 65536; cabecera 32; alineación 16; vivos 3
  offset     0: total    96; ocupado
  offset    96: total   160; ocupado
  offset   256: total    96; ocupado
  offset   352: total 65184; libre
Lista libre: 352 -> NULL
... pasos intermedios ...
4. Todos liberados y fusionados:
Capacidad 65536; cabecera 32; alineación 16; vivos 0
  offset     0: total 65536; libre
Lista libre: 0 -> NULL
Comprobaciones correctas.

La salida es ilustrativa para A = 16 y H = 32. Después de liberar B, la lista libre contiene los offsets 96 y 352. Al pedir 48 bytes, se necesitan 80 en total; el hueco de 160 se convierte en un ocupado de 80 y otro libre de 80. La lista pasa a enlazar 176 y 352.

Al liberar d se recupera el hueco original. Al liberar a se fusiona hacia la derecha. Cuando c se libera, conecta el espacio libre anterior con la cola: queda un único bloque de 65 536 bytes.

$ strace -e trace=mmap,munmap,brk ./lista_libre
... actividad del cargador y de la biblioteca ...
mmap(NULL, 65536, PROT_READ|PROT_WRITE,
     MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7f...
... asignaciones, liberaciones y volcados de la demostración ...
munmap(0x7f..., 65536) = 0

Nuestras asignaciones y liberaciones intermedias no llaman al núcleo para cambiar la región. Los printf de inspección y el arranque pueden producir otras llamadas de libc; no deben atribuirse a mi_malloc. Para detectar accesos desalineados y otros errores instrumentables también puedes compilar con -fsanitize=undefined -g.

Un sanitizador no conoce automáticamente los límites de cada subasignación dentro del mmap. Por eso no se debe suponer que detectará todo desbordamiento entre nuestros bloques: hacen falta comprobaciones específicas de las invariantes y de los patrones de datos. El proyecto del tema 51 ampliará las pruebas de estrés.

11. Simulador de lista libre

Este modelo representa una región de 1024 bytes, alineación de 16 y cabeceras de 32. Sigue las mismas reglas de primer ajuste, tamaño total, resto mínimo de 48 bytes y fusión inmediata. La tabla muestra el orden físico; la línea de lista libre enlaza solo los huecos.

La demostración asigna 64, 128 y 64 bytes, libera el segundo bloque y pide 48. Observa la nueva cabecera en el offset 176. Después libera los bloques vivos en distintos órdenes y verifica que el estado final sea una única cabecera en cero con 992 bytes de capacidad útil.

Para explorar el resto mínimo, reinicia y pide 960 bytes: se necesitan 992 contando cabecera, pero sobran solo 32. Se entrega el bloque completo de 1024, con capacidad de datos 992 y relleno de 32 respecto de lo pedido. Pedir 944, en cambio, deja exactamente 48 y permite un nuevo bloque libre con 16 bytes útiles.

Las métricas satisfacen esta identidad: útil vivo + relleno ocupado + capacidad libre + cabeceras = 1024. Al fusionar, disminuyen las cabeceras y aumenta la capacidad útil libre. El simulador almacena los bloques en un arreglo para dibujarlos, pero deriva de ellos la misma lista libre ordenada; no representa punteros reales ni asignaciones del navegador.

12. Fragmentación y costo

La fragmentación interna aparece por la alineación y por los restos demasiado pequeños para dividir. Las cabeceras son otro costo de administración, que conviene medir por separado. La fragmentación externa aparece cuando hay varios huecos separados por bloques vivos y ninguno alcanza para una petición.

Pedir 224, 224, 224, 224: cuatro bloques de 256, sin espacio sobrante.
Liberar el primero y el tercero: dos huecos de 256 separados.
Capacidad útil libre total: 224 + 224 = 448 bytes.
Pedir 300: necesario = redondear(300 + 32, 16) = 336.
No hay un hueco de 336: la petición falla aunque 448 sea mayor que 300.

La fusión elimina separaciones entre huecos contiguos, pero no puede atravesar bloques ocupados. Compactar moviendo esos objetos invalidaría punteros de la aplicación; nuestro asignador no conoce todas las referencias para actualizarlas.

Si hay F bloques libres, la búsqueda por primer ajuste cuesta O(F) en el peor caso. Insertar una liberación en orden también cuesta O(F). Encontrados los vecinos, las fusiones son O(1). El volcado físico recorre todos los bloques y no forma parte del costo necesario de una reserva normal.

Elegimos simplicidad para poder verificar las operaciones. Asignadores reales pueden usar clases de tamaño, listas separadas, cachés y otras estructuras para reducir búsquedas y contención. Esas decisiones añaden complejidad y cambian el consumo y la fragmentación.

13. Errores, limitaciones y extensiones

Una pila de bytes declarada como static unsigned char memoria[...]; no sustituye sin más este diseño: hay que considerar alineación y reglas de tipo efectivo al alojar objetos. Aquí dependemos de las interfaces de memoria de Linux y de un mapeo sin tipo declarado; no presentamos el archivo como C portable a cualquier plataforma sin adaptaciones.

Para soportar crecimiento mediante varias regiones habría que llevar un registro de ellas, evitar fusiones entre mapeos distintos y saber cuándo una región completa está libre. Una dirección virtual contigua por casualidad no autoriza a tratar dos reservas independientes como un único objeto administrado.

Agregar calloc requiere comprobar la multiplicación y poner a cero el tamaño solicitado. Agregar realloc exige conservar los bytes existentes, manejar el fallo sin perder el bloque original y quizá ampliar sobre un vecino libre. Esas extensiones deben definir su contrato y sus pruebas; no se obtienen renombrando mi_malloc.

Referencias para revisar los contratos subyacentes: mmap y munmap en Linux, la familia malloc y el borrador público N1570 de C11, en particular los apartados sobre alineación, max_align_t y almacenamiento asignado. El ejemplo se compila como C17 y usa esas características del lenguaje.

14. Resumen

• Una región obtenida con mmap puede subdividirse sin hacer una llamada al sistema por cada objeto.
• La cabecera guarda el tamaño total, estado y enlace libre; los datos empiezan después de ella.
• La alineación debe conservarse en la base, las cabeceras y todos los desplazamientos.
• El primer ajuste busca el primer hueco suficiente y actualiza el enlace que lo referencia.
• Solo se divide si el resto alcanza para otra cabecera y una capacidad útil mínima.
• La lista libre ordenada facilita encontrar vecinos, pero la fusión exige contigüidad física.
• Fusionar recupera espacio administrativo sin mover los objetos ocupados.
• Las invariantes conectan el mapa físico, la lista y el contador de bloques vivos.
• La capacidad libre total no garantiza que exista un hueco contiguo suficiente.
• La implementación es de un hilo, capacidad fija y contrato limitado; no reemplaza a libc.

15. Preguntas de repaso

Intenta responder antes de abrir cada explicación.

Para practicar

1. Compila el programa, anota H y A en tu entorno y recalcula los offsets de la demostración.
2. Prueba tamaños 1, A - 1, A y A + 1. Comprueba la alineación de cada puntero y preserva un patrón de datos diferente en cada bloque vivo.
3. Libera tres bloques consecutivos en todos los órdenes posibles. Verifica que la región termine como un único hueco cuando no haya otros objetos vivos.
4. Reproduce en el simulador la división con resto de 48 y la absorción de un resto de 32. Explica cómo cambia el costo en cabeceras y relleno.
5. Reproduce el caso de cuatro peticiones de 224, dos huecos separados y una petición fallida de 300.
6. Escribe una función de comprobación que recorra el mapa físico y la lista, y verifique las invariantes después de cada operación.
7. Agota la región con peticiones pequeñas y después libéralas. Comprueba que el fallo no cambie los bloques ya vivos.
8. Prueba SIZE_MAX y valores cercanos sin intentar escribir en un resultado NULL. Explica qué suma o redondeo debe rechazarlos.
9. Diseña cómo registrarías varias regiones sin fusionar bloques de reservas independientes. Deja la implementación completa y el estrés para el proyecto del tema 51.