Allocation dynamique

Un programme lit un nombre au clavier, puis doit stocker autant de valeurs. Avec les outils du bloc III, c'est impossible : la taille d'un tableau est fixée à la compilation, et l'on ne peut que surdimensionner au hasard — int T[1000], en espérant que mille suffira et en gaspillant si l'utilisateur en saisit trois.

La tentation suivante est pire :

1int *creer(int n) {2    int T[n];3    return T;                    /* l'adresse d'une variable LOCALE */4}

Le tableau vit dans le cadre d'appel, qui est détruit au retour. La fonction rend l'adresse d'une case qui n'existe plus — un pointeur pendant au sens du chapitre 7. Le programme compile, souvent s'exécute, et corrompt sa mémoire.

Ce chapitre donne la réponse correcte : allouer dans une zone dont on décide soi-même de la durée de vie.

Deux zones, deux régimes

Le chapitre 3 du cours de systèmes a décrit l'image mémoire d'un processus. Deux de ses régions nous intéressent.

1  ┌────────────────────┐2  │  pile (stack)      │  variables locales, paramètres, adresses de retour3  │        ↓           │  gérée AUTOMATIQUEMENT : allouée à l'entrée d'un4  │                    │  bloc, libérée à sa sortie5  │        ↑           │6  │  tas (heap)        │  allocation dynamique7  └────────────────────┘  gérée À LA MAIN : vous allouez, vous libérez

La ligne décisive est la troisième. Sur le tas, la donnée survit à la fonction qui l'a créée — c'est précisément ce qu'il fallait, et c'est ce que la pile ne peut pas offrir.

Le prix est dans la deuxième ligne, et c'est tout le chapitre : ce que vous allouez, vous devez le rendre.

Les quatre fonctions

1#include <stdlib.h>2 3int *T = malloc(n * sizeof(int));      /* n int, contenu INDÉFINI */4int *U = calloc(n, sizeof(int));       /* n int, tous mis à ZÉRO */5T = realloc(T, m * sizeof(int));       /* redimensionne à m int */6free(T);                                /* rend la mémoire */

Quatre remarques, une par ligne.

malloc ne connaît pas les types : elle prend un nombre d'octets et rend un pointeur générique. D'où l'idiome n * sizeof(int), et la variante préférable n * sizeof(*T) — qui reste correcte si le type de T change un jour.

Son contenu est indéfini, comme une variable locale. calloc met à zéro, ce qui coûte un peu et évite une classe d'erreurs ; on la préfère dès que le zéro a un sens.

realloc peut déplacer le bloc. S'il n'y a pas la place de l'agrandir sur place, elle en alloue un autre ailleurs, recopie, et libère l'ancien : tous les pointeurs vers l'ancien emplacement deviennent pendants. Elle a aussi un piège d'écriture — T = realloc(T, ...) perd le pointeur original si l'allocation échoue et que NULL est rendu. On écrit donc dans une variable temporaire, qu'on n'affecte à T qu'après vérification.

malloc peut échouer et rendre NULL. Le tester n'est pas une politesse : déréférencer le résultat sans vérifier transforme une pénurie de mémoire — situation gérable — en erreur de segmentation.

1int *T = malloc(n * sizeof(*T));2if (T == NULL) { fprintf(stderr, "mémoire insuffisante\n"); return 1; }

Qui libère ?

C'est la vraie difficulté du chapitre, et elle n'est pas technique.

Le C n'a pas de ramasse-miettes : la propriété d'un bloc est une convention, portée par la documentation et rien d'autre. Une fonction qui rend un pointeur alloué doit dire, en toutes lettres, que l'appelant devra le libérer. Une fonction qui reçoit un pointeur doit dire si elle le libère ou non.

1/* Rend une chaîne allouée : à libérer par l'appelant. */2char *dupliquer(const char *source);

Trois règles de discipline évitent l'essentiel des dégâts.

Un malloc, un free, et si possible dans la même fonction ou dans la fonction jumelle — creerPile et detruirePile. Une allocation dont la libération est ailleurs, dans un autre fichier, écrit par quelqu'un d'autre, est une fuite en puissance.

Libérer dans l'ordre inverse de la construction, surtout pour les structures imbriquées : libérer une liste chaînée demande de garder le pointeur suivant avant de libérer la cellule, faute de quoi on le lit dans un bloc déjà rendu.

Mettre à NULL après free. free(p) ne modifie pas p : il rend la mémoire, et p continue de pointer dessus — pointeur pendant. Poser p = NULL transforme une utilisation ultérieure en erreur de segmentation immédiate, donc diagnosticable, et rend le double free inoffensif puisque free(NULL) ne fait rien.

Les quatre fautes

Elles portent des noms, et le chapitre 10 donnera l'outil qui les détecte.

La fuite (memory leak) : un bloc alloué que plus aucun pointeur ne désigne. Il reste occupé jusqu'à la fin du programme. Sans conséquence sur un utilitaire qui s'arrête, fatal sur un service qui tourne des mois.

Le pointeur pendant : utiliser un bloc après free. Le comportement dépend de ce que l'allocateur a fait de la place entre-temps — d'où des bogues qui apparaissent et disparaissent selon la charge.

Le double free : libérer deux fois le même bloc corrompt les structures internes de l'allocateur, et le plantage survient bien plus tard, ailleurs.

Le débordement de tas : écrire au-delà du bloc alloué. Même mécanisme qu'au chapitre 5, mais sur le tas, où l'on écrase les métadonnées de l'allocateur.

Le point commun des quatre : la faute et le symptôme sont éloignés. C'est précisément pourquoi valgrind existe, et pourquoi le chapitre 10 lui est en partie consacré.

Deux structures qui deviennent possibles

Le tableau dynamique. On alloue une capacité initiale, et quand elle est atteinte on double avec realloc. Doubler plutôt qu'ajouter une case est ce qui rend l'insertion amortie en $O(1)$ : $n$ insertions coûtent au total $O(n)$, puisque les recopies successives forment une série géométrique. C'est ainsi que sont faits les tableaux extensibles de tous les langages, et c'est le « $O(1)$ amorti » du chapitre 5 d'Algorithmique 2.

La liste chaînée. La cellule du chapitre 5 d'Algorithmique 2 devient enfin implémentable :

1typedef struct Cellule {2    int valeur;3    struct Cellule *suivant;     /* le chaînage : un pointeur */4} Cellule;5 6Cellule *n = malloc(sizeof(*n));7n->valeur = 12;8n->suivant = tete;               /* d'abord raccrocher la suite */9tete = n;                        /* puis déplacer la tête */

Les deux dernières lignes sont exactement celles du cours d'algorithmique, dans le même ordre — et l'on voit maintenant pourquoi il compte : tete = n d'abord rendrait l'ancienne liste inatteignable, donc définitivement fuite, puisque plus aucun pointeur ne la désignerait.

La flèche -> est une commodité : n->valeur s'écrirait sinon (*n).valeur, avec des parenthèses obligatoires car . est plus prioritaire que *.

À vous

L'exercice écrit un allocateur miniature — une zone découpée en blocs, avec malloc et free — puis l'instrumente pour détecter les quatre fautes. C'est un valgrind en trente lignes, et c'est ce qui rend les fautes visibles avant le chapitre 10.

Quatre temps. Allouer, écrire, libérer, et constater qu'un bilan de fin de programme signale les blocs jamais rendus. Provoquer un pointeur pendant, puis un double free, et voir l'allocateur les diagnostiquer. Écrire le tableau dynamique qui double sa capacité, et compter les recopies pour vérifier qu'elles sont bien en $O(n)$ au total. Enfin, construire et libérer une liste chaînée — en gardant le pointeur suivant avant de libérer la cellule, sinon l'allocateur vous le dira.

// ── Un allocateur instrumenté ─────────────────────────────────────────────
function creerAllocateur() {
  const blocs = new Map();     // adresse -> { taille, vivant, contenu }
  const fautes = [];
  let prochaine = 0x2000;

  return {
    malloc(octets) {
      const adresse = prochaine;
      prochaine += octets + 16;                  // + marge, comme un vrai tas
      blocs.set(adresse, { taille: octets, vivant: true, contenu: new Array(octets).fill(null) });
      return adresse;
    },
    calloc(n, taille) {
      const a = this.malloc(n * taille);
      blocs.get(a).contenu.fill(0);
      return a;
    },
    ecrire(adresse, decalage, valeur) {
      const b = blocs.get(adresse);
      if (!b) { fautes.push("écriture à une adresse jamais allouée"); return; }
      if (!b.vivant) { fautes.push("ÉCRITURE APRÈS LIBÉRATION à 0x" + adresse.toString(16)); return; }
      // ← à écrire : refuser un décalage hors du bloc (débordement de tas)
      b.contenu[decalage] = valeur;
    },
    lire(adresse, decalage) {
      const b = blocs.get(adresse);
      if (!b) { fautes.push("lecture à une adresse jamais allouée"); return undefined; }
      if (!b.vivant) { fautes.push("LECTURE APRÈS LIBÉRATION à 0x" + adresse.toString(16)); return undefined; }
      return b.contenu[decalage];
    },
    free(adresse) {
      const b = blocs.get(adresse);
      if (!b) { fautes.push("free d'une adresse jamais allouée"); return; }
      // ← à écrire : détecter le double free
      b.vivant = false;
    },
    bilan() {
      let fuite = 0, n = 0;
      for (const [a, b] of blocs) if (b.vivant) { fuite += b.taille; n++; }
      console.log("   " + n + " bloc(s) jamais libéré(s), " + fuite + " octets perdus");
      for (const f of fautes) console.log("   FAUTE : " + f);
      if (n === 0 && fautes.length === 0) console.log("   aucune fuite, aucune faute");
    },
  };
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Complétez la détection du débordement de bloc et du double free.
// 2. Écrivez un tableau dynamique qui DOUBLE sa capacité, et comptez les
//    recopies pour n insertions. Comparez à la stratégie « + 1 case ».
// 3. Construisez puis libérez une liste chaînée. Attention à l'ordre :
//    lire le champ « suivant » AVANT de libérer la cellule.

const A = creerAllocateur();
const t = A.malloc(4 * 5);
A.ecrire(t, 0, 42);
console.log("relu :", A.lire(t, 0));
A.free(t);
A.bilan();

En travaux pratiques

Ce que la suite en fait

Le bloc V donne aux données une forme et une persistance : la structure struct regroupe des champs de types différents — et l'on vient déjà d'en écrire une, la cellule de liste — puis les fichiers les font survivre à la fin du programme.

Le chapitre 10 fournit enfin l'outillage. valgrind détecte exactement les quatre fautes de ce chapitre, sur du vrai code, sans instrumentation à écrire soi-même — et il donne la ligne de l'allocation fautive, ce qui est la seule information réellement utile quand la faute et le symptôme sont à mille lignes l'un de l'autre.

À retenir