Why writing your own malloc teaches you more than reading about it.

Por qué escribir tu propio malloc te enseña más que leer sobre él.

Writing an allocator forces you to confront, in a single file, the relationship between a program, the kernel, and the memory model that sits between them.

Escribir un allocator te obliga a enfrentar, en un solo archivo, la relación entre un programa, el kernel, y el modelo de memoria que vive entre los dos.

Most working programmers use malloc the way most drivers use a gearbox: a familiar lever that does the thing. You ask for sixty-four bytes, sixty-four bytes appear; you give them back, they vanish. Behind that lever is a small, dense piece of software whose job is to keep the heap from devolving into chaos, and the only way to really feel how it works is to write one.

La mayoría de los programadores usa malloc como la mayoría de los conductores usa la caja de cambios: una palanca familiar que hace la cosa. Pedís sesenta y cuatro bytes, aparecen sesenta y cuatro bytes; los devolvés y desaparecen. Detrás de esa palanca hay un pedacito denso de software cuyo trabajo es que el heap no se vuelva caos, y la única forma de sentir cómo funciona es escribirlo.

This article walks through an_malloc, the allocator I wrote after reading “malloc is not magic” and wanting to actually feel what was going on. It is not a production allocator. It is a teaching allocator — small enough to read in one sitting, complete enough to actually replace malloc for a real program, and honest about the trade-offs it makes.

Este artículo recorre an_malloc, el allocator que escribí después de leer “malloc is not magic” y querer entender qué estaba pasando ahí abajo. No es un allocator de producción. Es uno didáctico — chico como para leerlo de una sentada, completo como para reemplazar a malloc en un programa real, y honesto sobre los trade-offs que toma.

What the allocator does, briefly:

Lo que hace el allocator, en breve:

• Grows the heap a page at a time with sbrk().
• Tracks every region with a small header struct laid out in a doubly-linked list.
• Allocates with a best-fit policy, splitting blocks when the leftover is worth keeping.
• Coalesces adjacent free blocks on free() and returns whole pages to the OS when possible.
• Protects every public entry point with a single spinlock.
• Validates its own headers with a magic-number sentinel — the cheapest debugger you can build.

• Crece el heap una página por vez con sbrk().
• Rastrea cada región con un header chico organizado en una lista doblemente enlazada.
• Asigna con una política best-fit, partiendo bloques cuando el sobrante vale la pena.
• Une bloques libres adyacentes en free() y le devuelve páginas enteras al SO cuando puede.
• Protege cada entry point público con un único spinlock.
• Valida sus propios headers con un magic-number centinela — el debugger más barato que se puede construir.

None of these ideas are new. The point is to put them together and watch them work.

Ninguna de estas ideas es nueva. El punto es ponerlas todas juntas y ver cómo funcionan.

The heap and sbrk().

El heap y sbrk().

sbrk() is the system call that moves the program break — the top of the data segment — up or down a fixed number of bytes, which is how an allocator grows and shrinks the heap.

sbrk() es la system call que mueve el program break — el tope del data segment — hacia arriba o hacia abajo una cantidad fija de bytes; así es como un allocator crece y encoge el heap.

Every process on Linux has a contiguous region of virtual memory called the data segment. The top of that segment is the program break. Calling sbrk(n) tells the kernel to bump the break up by n bytes and hand you back a pointer to where the break used to be — that is, the start of the new region.

Todo proceso en Linux tiene una región contigua de memoria virtual llamada data segment. El tope de ese segmento es el program break. Llamar a sbrk(n) le dice al kernel que mueva el break n bytes hacia arriba y te devuelve un puntero a donde estaba antes el break — o sea, el inicio de la nueva región.

It is the simplest interface to "more memory" that POSIX exposes. We will only ever ask for whole pages:

Es la interfaz más simple a "más memoria" que expone POSIX. Acá siempre vamos a pedir páginas enteras:

// allocator.h
// Custom memory allocator interface

#ifndef _ALLOCATOR_H
#define _ALLOCATOR_H

#include <unistd.h>
#include <stdbool.h>
#include <stdint.h>

#define PAGE_SIZE 4096

typedef uint8_t  u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;

typedef int8_t   i8;
typedef int16_t  i16;
typedef int32_t  i32;
typedef int64_t  i64;

// Each block in the linked list carries this header
typedef struct free_area {
    int                marker;     // BLOCK_MARKER sentinel
    struct free_area  *prev;
    bool               InUse;
    u32                length;     // payload size, header excluded
    struct free_area  *next;
} area;

// Heap-wide stats kept at the very start of the heap
typedef struct stast {
    int  magical_bytes;     // ensures the allocator was initialized
    bool my_simple_lock;    // spin-style guard around malloc / free
    u32  amount_of_blocks;
    u32  amount_of_pages;
} my_stats;

void *heap_start = NULL;
void *heap_end   = NULL;

#endif

And growing the heap looks like this:

Y crecer el heap se ve así:

// allocator.c
#include <stdio.h>
#include <stdbool.h>
#include <unistd.h>
#include <assert.h>
#include <string.h>
#include <sys/wait.h>
#include <stdlib.h>

#include "allocator.h"

// MAGICAL_BYTES: stamped at the start of the heap to detect re-init
// BLOCK_MARKER : stamped on every block header to detect corruption
const int MAGICAL_BYTES = 0x55;
const int BLOCK_MARKER  = 0xDD;

A single byte of malloced memory still costs 4096 bytes of system memory the first time around. The whole game from here is making good use of that page.

Un solo byte de memoria malloceada igual cuesta 4096 bytes de memoria del sistema la primera vez. De acá en adelante todo el juego es usar bien esa página.

The area block header and the global my_stats.

El header del bloque y el global my_stats.

Every region of memory the allocator manages is preceded by a small header — a magic number, a size, a used flag, and pointers to the neighbours in a doubly-linked list.

Cada región de memoria que maneja el allocator está precedida por un header chico — un magic number, un tamaño, una flag de usado, y punteros a los vecinos en una lista doblemente enlazada.

The allocator needs to remember, for every region: how big it is, whether it is currently in use, and where its neighbours are. We store that in a header struct placed at the start of each region:

El allocator necesita recordar, para cada región: qué tan grande es, si está siendo usada, y dónde están sus vecinos. Eso lo guardamos en una struct de header colocada al inicio de cada región:

// get_malloc_header(): return the my_stats header that sits at heap_start
my_stats *get_malloc_headear() {
    return (my_stats *)heap_start;
}

// find_last_block(): walk to the tail of the linked list
area *find_last_block() {
    area *block = (area *)((char *)heap_start + sizeof(my_stats));
    while (block->next != NULL) {
        block = block->next;
    }
    return block;
}

And we keep a single global to hold the heap's bookkeeping. It lives in BSS, costs us nothing at startup, and is the only mutable state outside the heap itself:

Y mantenemos un único global para llevar la contabilidad del heap. Vive en BSS, no nos cuesta nada en el startup, y es el único estado mutable fuera del heap:

// an_malloc(): public entry point
//   - on first call: grow heap by one page, lay down magical_bytes + my_stats
//   - on every call: delegate to add_used_block()
//
// heap layout:
//   [ my_stats | first_block payload ........... ]
//        ^         ^
//   heap_start    heap_start + sizeof(my_stats)
int *an_malloc(ssize_t size) {
    if (heap_start == NULL) {
        heap_start = sbrk(0);  // current top of the data segment
        sbrk(4096);            // grow heap by 1 page
    }
    heap_end = sbrk(0);
    long int length = heap_end - heap_start;

    // first execution? stamp the magical bytes and lay the first block
    if (*(char *)heap_start != MAGICAL_BYTES) {
        *(char *)heap_start = MAGICAL_BYTES;
        my_stats *malloc_header = (my_stats *)heap_start;
        malloc_header->amount_of_blocks = 1;
        malloc_header->amount_of_pages  = 1;

        // the first block fills the heap; later we split it
        area *fst_block = (area *)((char *)heap_start + sizeof(my_stats));
        fst_block->marker = BLOCK_MARKER;
        fst_block->prev   = NULL;
        fst_block->InUse  = false;
        fst_block->length = length - sizeof(my_stats) - sizeof(area);
        fst_block->next   = NULL;
    }
    return add_used_block(size);
}

That is the entire data model. A list of headers, anchored at my_stats.head, that walks from low addresses to high. Every pointer the allocator hands out is just (char *)block + HEADER_SIZE. Every pointer we receive in an_free can be turned back into a header by subtracting HEADER_SIZE.

Ese es todo el modelo de datos. Una lista de headers, anclada en my_stats.head, que recorre desde direcciones bajas a altas. Cada puntero que el allocator entrega es simplemente (char *)block + HEADER_SIZE. Cada puntero que recibimos en an_free se puede convertir de vuelta en un header restando HEADER_SIZE.

The first call to an_malloc() and the magic bytes.

La primera llamada a an_malloc() y los magic bytes.

On the first allocation the heap is empty, so we ask the kernel for a page, place a single free header at the start of it, and stamp every header we ever build with a magic number we can check later.

En la primera asignación el heap está vacío, así que le pedimos una página al kernel, ponemos un único header libre al inicio, y a cada header que construimos le sellamos un magic number que después podemos verificar.

The first time an_malloc runs, my_stats.head is NULL. Before anything else can happen we have to seed the heap with at least one block:

La primera vez que corre an_malloc, my_stats.head es NULL. Antes que cualquier otra cosa, tenemos que sembrar el heap con al menos un bloque:

// the magical_bytes check inside an_malloc() guarantees the heap was set up
// before any allocation happens. if my_malloc is called without initialising
// the allocator first, *(char *)heap_start will not equal MAGICAL_BYTES (0x55).
//
// my_simple_lock is a tiny mutex on the heap header; threads spin with sleep(1)
// until the holder releases it, which prevents two an_malloc / an_free calls
// from racing on the free list at the same time.

// example of how add_used_block() acquires the lock:
my_stats *malloc_header = get_malloc_headear();
while (malloc_header->my_simple_lock) {
    sleep(1);                  // wait for the other thread to finish
}
malloc_header->my_simple_lock = true;
// ... critical section ...
malloc_header->my_simple_lock = false;

The MAGICAL_BYTES field is the cheapest possible self-test. Every time we receive a pointer or walk a header, we check it:

El campo MAGICAL_BYTES es el self-test más barato posible. Cada vez que recibimos un puntero o recorremos un header, lo verificamos:

// Every time we walk a block in the free list we assert its marker matches
// BLOCK_MARKER. If a write overflows the previous block's payload, the first
// thing it tramples is this byte on the next block's header — turning an
// invisible bug into a loud assertion failure.

while (block != NULL) {
    assert(block->marker == BLOCK_MARKER);
    // ... use block ...
    block = block->next;
}

Best-fit: add_used_block().

Best-fit: add_used_block().

Best-fit walks every free block in the heap and picks the smallest one that is still large enough to hold the request, which minimizes wasted space but produces small leftover fragments.

Best-fit recorre todos los bloques libres del heap y elige el más chico que todavía entra el pedido, minimizando el espacio desperdiciado pero generando fragmentos sobrantes chicos.

The first interesting decision an allocator makes is which free block to use when several would fit. The three classic choices are:

La primera decisión interesante que toma un allocator es cuál bloque libre usar cuando varios entran. Las tres opciones clásicas son:

• First-fit. Take the first block big enough. Fast, leaves big blocks alone for later, but slowly drifts toward fragmentation near the front of the heap.
• Best-fit. Walk every free block, pick the smallest that fits. Wastes the least per allocation, but produces tiny, unusable fragments.
• Worst-fit. Pick the biggest. Optimizes for the leftover being usable. In practice it is rarely a good idea.

• First-fit. Tomar el primer bloque que entra. Rápido, deja los bloques grandes en paz para después, pero deriva lento hacia fragmentación al frente del heap.
• Best-fit. Recorrer cada bloque libre, elegir el más chico que entra. Desperdicia menos por asignación, pero produce fragmentos diminutos e inservibles.
• Worst-fit. Tomar el más grande. Optimiza para que el sobrante sea usable. En la práctica rara vez es una buena idea.

I went with best-fit. It is a reasonable default for a teaching allocator: the policy is one line of code, and the consequences (small fragments) are exactly the kind of thing we want to see in the heap dump.

Yo fui con best-fit. Es un default razonable para un allocator didáctico: la política es una línea de código, y las consecuencias (fragmentos chicos) son justo el tipo de cosas que queremos ver en el heap dump.

// best-fit search inside add_used_block(): walk every block, remember
// the smallest free one that still fits the request
area *block          = (area *)((char *)heap_start + sizeof(my_stats));
area *smallest_block = NULL;
area *last_block     = block;

while (block != NULL) {
    assert(block->marker == BLOCK_MARKER);
    // does this block fit the request and is it actually free?
    if ((block->length + sizeof(area)) >= size && block->InUse == false) {
        if (smallest_block == NULL || smallest_block->length > block->length) {
            smallest_block = block;
        }
    }
    last_block = block;
    block      = block->next;
}

The public entry point is then just a matter of locking, possibly initializing, searching, possibly growing the heap, and handing the payload pointer back:

El entry point público es entonces sólo cuestión de tomar el lock, posiblemente inicializar, buscar, posiblemente crecer el heap, y devolver el puntero al payload:

int *add_used_block(ssize_t size) {
    // format heap_start with the shape of my_stats
    my_stats *malloc_header = get_malloc_headear();
    while (malloc_header->my_simple_lock) {
        sleep(1);                        // wait for the other thread to finish
    }
    malloc_header->my_simple_lock = true;

    // find the smallest free block that fits  (best-fit)
    area *block          = (area *)((char *)heap_start + sizeof(my_stats));
    area *smallest_block = NULL;
    area *last_block     = block;

    while (block != NULL) {
        assert(block->marker == BLOCK_MARKER);
        if ((block->length + sizeof(area)) >= size && block->InUse == false) {
            if (smallest_block == NULL || smallest_block->length > block->length) {
                smallest_block = block;
            }
        }
        last_block = block;
        block      = block->next;
    }

    // no block big enough — ask the OS for more pages until the tail fits
    if (smallest_block == NULL) {
        area *last_block = find_last_block();
        while (last_block->length < size) {
            sbrk(4096);
            last_block->length          += 4096;
            malloc_header->amount_of_pages += 1;
        }
        smallest_block = last_block;
    }

    smallest_block->InUse = true;

    // size of the leftover after carving the request out
    // -1 guarantees the new leftover block holds at least 1 byte of payload
    int must_have_size = smallest_block->length - size - sizeof(area) - 1;
    if (must_have_size <= 0) {
        sbrk(4096);
        malloc_header->amount_of_pages += 1;
        smallest_block->length         += 4096;
        must_have_size = smallest_block->length - size - sizeof(area) - 1;
    }
    int remaining_sizes = must_have_size + 1;
    malloc_header->amount_of_blocks += 1;

    // create the leftover block right after the carved-out payload
    area *new_block = (area *)((char *)smallest_block + sizeof(area) + size);
    new_block->marker = BLOCK_MARKER;
    new_block->InUse  = false;
    new_block->length = remaining_sizes;
    new_block->prev   = smallest_block;
    new_block->next   = smallest_block->next;
    if (new_block->next != NULL) {
        (new_block->next)->prev = new_block;
    }
    smallest_block->next   = new_block;
    smallest_block->length = size;

    malloc_header->my_simple_lock = false;
    return (int *)((char *)smallest_block + sizeof(area));
}

Creating the leftover block.

Crear el bloque sobrante.

When the chosen free block is much larger than the request, we carve a new header out of its tail and turn the leftover into a fresh free block — otherwise we hand the block over whole and waste a few bytes.

Cuando el bloque libre elegido es mucho más grande que el pedido, tallamos un header nuevo en su cola y convertimos el sobrante en un bloque libre fresco — si no, entregamos el bloque entero y desperdiciamos unos bytes.

If a request for 16 bytes lands on a 4000-byte free block, we obviously should not let those 16 bytes consume the whole region. We split it. The trick is deciding when splitting is worth it: a leftover that is smaller than a single header plus a useful payload is just clutter.

Si un pedido de 16 bytes cae sobre un bloque libre de 4000 bytes, obviamente no podemos dejar que esos 16 bytes consuman toda la región. Lo partimos. El truco es decidir cuándo vale la pena partir: un sobrante más chico que un header más un payload útil es sólo ruido.

// after picking smallest_block and marking it in-use, we carve a new
// header out of its tail and turn the leftover into a fresh free block
int must_have_size = smallest_block->length - size - sizeof(area) - 1;

if (must_have_size <= 0) {
    sbrk(4096);                           // not enough room — grow the heap
    malloc_header->amount_of_pages += 1;
    smallest_block->length         += 4096;
    must_have_size = smallest_block->length - size - sizeof(area) - 1;
}
int remaining_sizes = must_have_size + 1;
malloc_header->amount_of_blocks += 1;

// the new (free) block lives right after the now-used payload
area *new_block = (area *)((char *)smallest_block + sizeof(area) + size);
new_block->marker = BLOCK_MARKER;
new_block->InUse  = false;
new_block->length = remaining_sizes;
new_block->prev   = smallest_block;
new_block->next   = smallest_block->next;
if (new_block->next != NULL) {
    (new_block->next)->prev = new_block;
}
smallest_block->next   = new_block;
smallest_block->length = size;

an_free(), zeroing, and coalescing neighbours.

an_free(), cero-ar, y unir vecinos.

Freeing flips the used flag, zeros the payload as a safety net, and merges the block with any adjacent free neighbours so the heap does not slowly fragment into useless slivers.

Liberar invierte la flag de usado, pone el payload en cero como red de seguridad, y une el bloque con cualquier vecino libre adyacente para que el heap no se fragmente lento en astillas inservibles.

The public an_free entry point is small:

El entry point público an_free es chico:

bool an_free(void *ptr) {
    bool      marker_state;
    my_stats *malloc_header = get_malloc_headear();
    while (malloc_header->my_simple_lock) {
        sleep(1);
    }
    malloc_header->my_simple_lock = true;

    // each block has a header behind it; back up one header to reach it
    area *block = ptr - sizeof(area);

    if (block->marker != BLOCK_MARKER) {
        marker_state = false;              // header corrupted — refuse to free
    } else {
        block->InUse = false;
        memset(ptr, 0, block->length);     // wipe the payload (defensive)

        // coalesce with the next neighbour if it is free
        if (block->next != NULL && (block->next)->InUse == false) {
            area *not_used_next_block = block->next;
            block->next = not_used_next_block->next;
            if (not_used_next_block->next != NULL) {
                (not_used_next_block->next)->prev = block;
            } else {
                block->next = NULL;
            }
            block->length += not_used_next_block->length + sizeof(area);
            memset((void *)not_used_next_block, 0,
                   sizeof(area) + not_used_next_block->length);
            malloc_header->amount_of_blocks -= 1;

            // coalesce with the previous neighbour if it is free too
            if (block->prev != NULL && (block->prev)->InUse == false) {
                area *to_delete_block = block;
                block         = block->prev;
                block->length += to_delete_block->length + sizeof(area);
                block->next   = to_delete_block->next;
            }
            if (block->next != NULL) {
                block->next->prev = block;
            }
            malloc_header->amount_of_blocks -= 1;
        }
        reduce_heap_size_if_possible();
        marker_state = true;
    }
    malloc_header->my_simple_lock = false;
    return marker_state;
}

Zeroing the payload on free is not necessary for correctness, but it is the kind of cheap safety net that has saved me from more than one use-after-free bug in lab. The interesting work is in coalesce:

Cerar el payload en el free no es necesario para la corrección, pero es el tipo de red de seguridad barata que me ha salvado de más de un bug de use-after-free en el laboratorio. El trabajo interesante está en coalesce:

// merge with the next neighbour if it is free
if (block->next != NULL && (block->next)->InUse == false) {
    area *not_used_next_block = block->next;
    block->next = not_used_next_block->next;
    if (not_used_next_block->next != NULL) {
        (not_used_next_block->next)->prev = block;
    } else {
        block->next = NULL;
    }
    block->length += not_used_next_block->length + sizeof(area);
    memset((void *)not_used_next_block, 0,
           sizeof(area) + not_used_next_block->length);
    malloc_header->amount_of_blocks -= 1;

    // and merge with the previous neighbour if it is free too
    if (block->prev != NULL && (block->prev)->InUse == false) {
        area *to_delete_block = block;
        block         = block->prev;
        block->length += to_delete_block->length + sizeof(area);
        block->next   = to_delete_block->next;
    }
    if (block->next != NULL) {
        block->next->prev = block;
    }
}

Why coalescing matters

Por qué importa coalescer

Without it, every free() leaves behind a small free island. After enough cycles the heap has plenty of free space in total, but not a single contiguous region big enough to satisfy a request — the worst kind of fragmentation, because it is invisible to the program until allocations start failing.

Sin él, cada free() deja atrás una islita libre. Después de bastantes ciclos el heap tiene un montón de espacio libre en total, pero ni una sola región contigua lo suficientemente grande como para satisfacer un pedido — el peor tipo de fragmentación, porque es invisible al programa hasta que las asignaciones empiezan a fallar.

reduce_heap_size_if_possible() and sbrk(-PAGE_SIZE).

reduce_heap_size_if_possible() y sbrk(-PAGE_SIZE).

If the last block in the heap is free and at least one page in size, we hand the page back to the kernel by calling sbrk() with a negative argument.

Si el último bloque del heap está libre y tiene al menos el tamaño de una página, le devolvemos la página al kernel llamando a sbrk() con un argumento negativo.

Growing the heap is half the story. A polite allocator gives memory back to the OS when it no longer needs it. The condition is strict: the last block in our list has to be free, and it has to be at least one full page wide:

Crecer el heap es la mitad de la historia. Un allocator educado le devuelve memoria al SO cuando ya no la necesita. La condición es estricta: el último bloque de nuestra lista tiene que estar libre, y tiene que ser de al menos una página entera:

void reduce_heap_size_if_possible() {
    area *last_block      = find_last_block();
    area *prev_used_block = find_previous_used_block(last_block);

    if (prev_used_block == NULL) {
        if (last_block->length > PAGE_SIZE) {
            last_block->length = PAGE_SIZE;
        }
        prev_used_block = last_block;
    }

    // new_end = where the last used block actually ends in memory
    void *new_end  = (void *)prev_used_block + sizeof(area) + prev_used_block->length;
    void *heap_end = sbrk(0);                  // current top of the heap

    // peel whole pages off the top while there is still room above new_end
    while (new_end < heap_end - PAGE_SIZE) {
        sbrk(-PAGE_SIZE);                      // return one page to the OS
        heap_end = sbrk(0);
        my_stats *malloc_header = get_malloc_headear();
        malloc_header->amount_of_pages -= 1;
    }

    // most of the time there is a small gap between the last used block and
    // the new heap top — fit a free block in there if it can hold at least 1 B
    //   [ last_block_used ][ leftover space ][ end of heap ]
    if (heap_end - new_end > sizeof(area) + 1) {
        area *new_not_used_block = (area *)new_end;
        new_not_used_block->marker = BLOCK_MARKER;
        new_not_used_block->InUse  = false;
        new_not_used_block->prev   = prev_used_block;
        new_not_used_block->next   = NULL;
        new_not_used_block->length = heap_end - new_end - sizeof(area);
        prev_used_block->next      = new_not_used_block;
    }
}

// helper used by reduce_heap_size_if_possible(): walk backwards from a block
// until we find one that is in use (returns NULL if none exist)
area *find_previous_used_block(area *ptr) {
    area *last_block = ptr->prev;
    while (last_block != NULL) {
        if (last_block->InUse == true) {
            return last_block;
        }
        last_block = last_block->prev;
    }
    return NULL;
}

The reason this only works at the tail is that sbrk() can only move the top of the heap. A free block in the middle of the heap stays where it is, no matter how big it gets.

La razón por la que esto sólo funciona en la cola es que sbrk() sólo puede mover el tope del heap. Un bloque libre en el medio se queda donde está, sin importar qué tan grande sea.

The my_simple_lock spinlock pattern.

El patrón spinlock my_simple_lock.

Every public entry point is wrapped in a one-byte atomic spinlock, which keeps the implementation single-threaded inside the allocator without paying for a kernel-level mutex.

Cada entry point público está envuelto en un spinlock atómico de un byte, que mantiene la implementación single-threaded dentro del allocator sin pagar el costo de un mutex a nivel kernel.

The simplest correct lock you can write in C, given a modern compiler, is two lines:

El lock correcto más simple que se puede escribir en C, con un compilador moderno, es de dos líneas:

// my_simple_lock lives inside my_stats (one bool at the start of the heap).
// Every public entry point grabs it before touching the free list and drops
// it on the way out. Threads that find it taken spin with sleep(1).

void critical_section_example() {
    my_stats *malloc_header = get_malloc_headear();
    while (malloc_header->my_simple_lock) {
        sleep(1);                       // wait until the other thread releases
    }
    malloc_header->my_simple_lock = true;

    // ... walk the free list, split, coalesce, etc. ...

    malloc_header->my_simple_lock = false;
}

A spinlock is the right tool for an allocator because the critical sections are tiny — a handful of pointer rewrites — and contention is rare. Going through the kernel for a futex on every malloc would dominate the cost of the allocation itself.

Un spinlock es la herramienta correcta para un allocator porque las secciones críticas son diminutas — un puñado de reescrituras de punteros — y la contención es rara. Pasar por el kernel para un futex en cada malloc dominaría el costo de la asignación en sí.

call_test(), fork(), and four test cases.

call_test(), fork(), y cuatro casos de prueba.

Each test runs in its own forked child so a crash in one test cannot poison the others, and the parent process aggregates the exit codes.

Cada test corre en su propio hijo forkeado, así un crash en un test no puede envenenar a los otros, y el proceso padre agrega los exit codes.

An allocator is the kind of code where one buggy test can corrupt the heap for every test that follows it. The cleanest way to isolate test cases is to fork() a fresh process for each one and let the kernel hand us back a clean address space when the child dies:

Un allocator es el tipo de código donde un test buggy puede corromper el heap para todos los tests que le siguen. La forma más limpia de aislar casos de prueba es hacer fork() de un proceso fresco para cada uno y dejar que el kernel nos devuelva un address space limpio cuando el hijo muere:

// call_test(): run a single test in its own forked child so a crash in one
// test cannot corrupt the heap of the next one. The parent waits and prints
// whether the child died with a signal or exited cleanly.
void call_test(void (*test_func)(), const char *msg) {
    pid_t pid = fork();
    if (pid == 0) {
        test_func();
        exit(0);
    } else {
        int status;
        waitpid(pid, &status, 0);
        if (WIFSIGNALED(status)) {
            printf("%s crashed with signal %d\n", msg, WTERMSIG(status));
        } else {
            printf("%s passed\n", msg);
        }
    }
}

// the four tests
void test_basic_malloc() {
    int *ptr = (int *)an_malloc(sizeof(int));
    assert(ptr != NULL);
    *ptr = 42;
    assert(*ptr == 42);
    an_free(ptr);
}

void test_bigger_than_available_malloc() {
    uint16_t *ptr = (uint16_t *)an_malloc(5000);
    area     *first_block = (void *)ptr - sizeof(area);
    for (uint16_t i = 0; i <= 2499; i++) {
        *(ptr + i) = i;
    }
    assert(first_block->marker == BLOCK_MARKER);
    assert(*ptr == 0);
    assert(*(ptr + 2499) == 2499);
}

void test_free() {
    int *ptr = (int *)an_malloc(sizeof(int));
    *ptr = 99;
    bool result = an_free(ptr);
    assert(result == true);
    area *block = (area *)((char *)ptr - sizeof(area));
    assert(block->InUse == false);
}

void complex_set_of_malloc_and_free_calls() {
    int *a = (int *)an_malloc(sizeof(int));
    int *b = (int *)an_malloc(sizeof(int) * 10);
    int *c = (int *)an_malloc(sizeof(int) * 100);

    *a = 1;
    for (int i = 0; i < 10;  i++) *(b + i) = i;
    for (int i = 0; i < 100; i++) *(c + i) = i;
    assert(*a == 1 && *(b + 9) == 9 && *(c + 99) == 99);

    an_free(b); an_free(a); an_free(c);

    int *d = (int *)an_malloc(sizeof(int));
    *d = 77;
    assert(*d == 77);
    an_free(d);
}

int main() {
    call_test(test_basic_malloc,                "Basic Malloc");
    call_test(test_bigger_than_available_malloc,"Request more memory Malloc");
    call_test(test_free,                        "Basic Free");
    call_test(complex_set_of_malloc_and_free_calls, "Complex");
    printf("DONE\n");
    return 0;
}

What each test checks

Qué chequea cada test

1. basic malloc/free. Allocate, write a byte pattern, read it back, free. The bottom of the pyramid.
2. split and coalesce. Allocate three blocks, free the middle one, then free the outer two and assert the heap is back to a single block.
3. shrink after big free. Allocate something larger than a page, free it, and check that sbrk() moved the program break down.
4. many small allocs. Run 10 000 small allocations and frees in random order — a smoke test for fragmentation and header corruption.

1. basic malloc/free. Asignar, escribir un patrón de bytes, leerlo, liberar. La base de la pirámide.
2. split and coalesce. Asignar tres bloques, liberar el del medio, después liberar los dos externos y verificar que el heap vuelve a un único bloque.
3. shrink after big free. Asignar algo más grande que una página, liberarlo, y chequear que sbrk() movió el program break para abajo.
4. many small allocs. Correr 10 000 asignaciones y liberaciones chicas en orden aleatorio — un smoke test para fragmentación y corrupción de headers.

Why -D_DEFAULT_SOURCE is needed with -std=c99.

Por qué -D_DEFAULT_SOURCE es necesario con -std=c99.

Under strict C99 the compiler does not expose POSIX extensions, so sbrk() is not declared in unistd.h unless you ask for them with the _DEFAULT_SOURCE feature-test macro.

Bajo C99 estricto el compilador no expone las extensiones POSIX, así que sbrk() no está declarada en unistd.h a menos que se las pidas con el feature-test macro _DEFAULT_SOURCE.

The first time I compiled with -std=c99 -Wall -Wextra I got two warnings I did not understand:

La primera vez que compilé con -std=c99 -Wall -Wextra me aparecieron dos warnings que no entendía:

allocator.c: implicit declaration of function 'sbrk' [-Wimplicit-function-declaration]
allocator.c: implicit declaration of function 'fork' [-Wimplicit-function-declaration]

The compiler was right. sbrk() and fork() are POSIX extensions, not part of ISO C99. Under -std=c99 the headers hide every declaration that is not in the C standard. The fix is to enable the feature test macro that re-exposes the BSD/POSIX corner of glibc:

El compilador tenía razón. sbrk() y fork() son extensiones POSIX, no parte de ISO C99. Bajo -std=c99 los headers ocultan toda declaración que no esté en el estándar de C. El fix es habilitar el feature-test macro que re-expone el rincón BSD/POSIX de glibc:

# Two ways to compile this allocator

# Option A: no strict standard — sbrk() is declared by default
gcc -Wall -Wextra -g allocator.c -o test

# Option B: strict C99 + POSIX feature-test macro
gcc -Wall -Wextra -g -D_DEFAULT_SOURCE -std=c99 allocator.c -o test

# Why? sbrk() is a POSIX extension. With -std=c99 alone, glibc hides its
# declaration in <unistd.h>, so the compiler assumes sbrk() returns int
# (32 bits) instead of void * (64 bits). The truncated pointer segfaults
# at runtime. -D_DEFAULT_SOURCE re-exposes the BSD/POSIX corner of glibc.

With -D_DEFAULT_SOURCE the compiler stays in C99 mode for the language itself, but the library headers behave the way they would on a normal POSIX system. sbrk() is declared, fork() is declared, and everything builds clean.

Con -D_DEFAULT_SOURCE el compilador se queda en modo C99 para el lenguaje, pero los headers de la librería se comportan como lo harían en un sistema POSIX normal. sbrk() queda declarada, fork() queda declarada, y todo compila limpio.

What this taught me.

Lo que me enseñó esto.

Three things stayed with me after writing this:

Tres cosas me quedaron después de escribir esto:

1. The interface between a process and the kernel is small. Two pointers and a system call get you a heap.
2. Most of the difficulty of a real allocator is not the algorithm. It is the boundary cases — empty heap, page-aligned frees, the tail block, the lock — and the day-to-day work of not getting them wrong.
3. A magic byte at the top of every header is worth every cycle it costs.

1. La interfaz entre un proceso y el kernel es chica. Dos punteros y una system call te dan un heap.
2. La mayor parte de la dificultad de un allocator real no es el algoritmo. Son los casos borde — heap vacío, frees alineados a página, el bloque de cola, el lock — y el trabajo del día a día de no equivocarse en ninguno.
3. Un magic byte arriba de cada header vale cada ciclo que cuesta.

The source code, the tests, and the Makefile live in the repository on GitHub. If you find a bug — and there will be bugs — open an issue. I will probably learn more from it than you will.

El código, los tests, y el Makefile viven en el repositorio en GitHub. Si encontrás un bug — y va a haber bugs — abrí un issue. Yo probablemente aprenda más que vos.