Étiquette : c

La première fois que j’ai écrit mon propre malloc, le concept de mémoire dynamique a cessé de ressembler à une boîte noire. Un allocateur n’est qu’un programme qui gère un gros bloc de mémoire et en distribue des morceaux à la demande. Les parties difficiles sont la comptabilité et la fragmentation, rien de mystique. Voici une version minimale.

D’où vient la mémoire

Votre allocateur a besoin de mémoire brute à découper. Sur Unix, vous l’obtenez du noyau avec sbrk, qui déplace le sommet du tas, ou avec mmap pour de plus grandes régions. sbrk est le plus simple à raisonner : appelez-le avec un nombre positif et le tas grandit, en retournant un pointeur vers le nouvel espace.

void *region = sbrk(4096);   // demande une page au noyau
if (region == (void *) -1) {
    // plus de mémoire
}

Tout le jeu consiste maintenant à prendre cette région et à la distribuer, en se souvenant des parties utilisées et des parties libres.

Les en-têtes de bloc : l’astuce centrale

L’idée fondamentale est de stocker des métadonnées juste avant chaque bloc distribué. Quand l’appelant demande N octets, vous réservez en réalité N octets plus la taille d’un petit en-tête. Vous retournez un pointeur situé après l’en-tête, donc l’appelant ne le voit jamais. Quand il appelle free avec ce pointeur, vous reculez pour retrouver l’en-tête.

typedef struct block {
    size_t size;          // taille utile en octets
    int free;             // 1 si disponible, 0 si utilisé
    struct block *next;   // bloc suivant dans la liste
} block_t;

#define HEADER_SIZE sizeof(block_t)

Je tiens une liste chaînée de ces en-têtes. Pour allouer, je parcours la liste à la recherche d’un bloc libre assez grand. C’est la stratégie first-fit : prendre le premier bloc qui convient. Le best-fit (le plus petit bloc qui rentre) gaspille moins d’espace mais est plus lent à chercher. Les deux conviennent pour apprendre.

Le chemin d’allocation

static block_t *head = NULL;

void *my_malloc(size_t size) {
    block_t *cur = head;
    while (cur) {
        if (cur->free && cur->size >= size) {
            cur->free = 0;
            return (void *)(cur + 1);   // mémoire juste après l'en-tête
        }
        cur = cur->next;
    }
    // rien de libre, agrandir le tas
    block_t *blk = sbrk(HEADER_SIZE + size);
    if (blk == (void *) -1) return NULL;
    blk->size = size;
    blk->free = 0;
    blk->next = head;
    head = blk;
    return (void *)(blk + 1);
}

L’expression cur + 1 est de l’arithmétique de pointeurs sur un pointeur block_t, donc elle saute exactement après l’en-tête. Si cette ligne semble étrange, mon article sur comment fonctionnent vraiment les pointeurs explique pourquoi ajouter un déplace d’une structure entière, pas d’un octet.

Libérer et le problème de la fragmentation

Libérer est presque trop facile : trouver l’en-tête et basculer le drapeau free. La mémoire n’est pas rendue au noyau, elle est simplement marquée réutilisable par la prochaine allocation.

void my_free(void *ptr) {
    if (!ptr) return;
    block_t *blk = (block_t *)ptr - 1;   // recule jusqu'à l'en-tête
    blk->free = 1;
}

Cette version naïve a un vrai défaut : la fragmentation. Libérez un bloc de 100 octets et un autre de 100 octets côte à côte, puis demandez 150 octets, et mon allocateur échoue alors même que 200 octets contigus sont libres. La correction est le coalescing : à la libération, vérifier si les blocs voisins sont aussi libres et les fusionner en un bloc plus grand. Les vrais allocateurs scindent aussi les blocs surdimensionnés pour qu’une demande de 16 octets ne consomme pas un morceau de 4 Ko.

L’alignement, le détail qui mord plus tard

Il y a un problème de correction que ma version jouet escamote : l’alignement. Le processeur attend qu’une valeur de huit octets se trouve à une adresse divisible par huit, et sur certaines architectures un accès mal aligné provoque une faute pure et simple. Un vrai allocateur arrondit chaque demande vers le haut pour que la zone utile commence toujours sur une frontière correctement alignée, généralement 16 octets sur un système 64 bits. Ma version marche par hasard parce que l’en-tête est déjà un multiple de l’alignement, mais dès que vous commencez à scinder des blocs, il faut arrondir les tailles, sinon vous rendez des adresses qui plantent sur certaines lectures. C’est le genre de bug qui se cache des mois puis ne surgit que sur une seule plateforme.

Pourquoi ça vaut la peine de le construire

• Vous cessez de craindre malloc et le voyez comme un composant réglable.
• Vous comprenez pourquoi les schémas d’allocation comptent pour la performance, ce qui rejoint directement conception orientée données et caches du processeur.
• Vous voyez exactement pourquoi le double-free et le use-after-free corrompent la mémoire : ils gribouillent sur ces en-têtes.

Les allocateurs de production comme jemalloc et tcmalloc ajoutent des classes de taille, des caches par thread et des structures astucieuses, mais le squelette est celui que je viens de décrire. Connaître le squelette, c’est la différence entre utiliser la mémoire et la comprendre.