Allocation dynamique

Point de départ

// ── 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();

Solution

function creerAllocateur() {
  const blocs = new Map();
  const fautes = [];
  let prochaine = 0x2000;
  let recopies = 0;

  return {
    malloc(octets) {
      const adresse = prochaine;
      prochaine += octets + 16;
      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; },
    realloc(adresse, octets) {
      const b = blocs.get(adresse);
      const neuf = this.malloc(octets);
      // realloc RECOPIE puis libère : c'est ce coût qu'on va compter.
      for (let i = 0; i < Math.min(b.taille, octets); i++) {
        blocs.get(neuf).contenu[i] = b.contenu[i];
        recopies++;
      }
      b.vivant = false;
      return neuf;
    },
    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; }
      // Débordement de tas : au-delà du bloc, on écrase les métadonnées de
      // l'allocateur, et le plantage survient bien plus tard, ailleurs.
      if (decalage < 0 || decalage >= b.taille) {
        fautes.push("DÉBORDEMENT DE BLOC : décalage " + decalage + " dans un bloc de " + b.taille);
        return;
      }
      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) {
      if (adresse === 0) return;                 // free(NULL) ne fait rien
      const b = blocs.get(adresse);
      if (!b) { fautes.push("free d'une adresse jamais allouée"); return; }
      if (!b.vivant) { fautes.push("DOUBLE FREE à 0x" + adresse.toString(16)); return; }
      b.vivant = false;
    },
    recopies: () => recopies,
    bilan(titre) {
      let fuite = 0, n = 0;
      for (const [, b] of blocs) if (b.vivant) { fuite += b.taille; n++; }
      console.log("   " + titre);
      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");
    },
  };
}

console.log("— 1. les quatre fautes —");
const A = creerAllocateur();
const t = A.malloc(4 * 5);
A.ecrire(t, 0, 42);
A.ecrire(t, 19, 7);        // décalage hors du bloc de 20 octets ? non : 19 < 20, ok
A.ecrire(t, 25, 7);        // débordement
A.free(t);
A.lire(t, 0);              // lecture après libération
A.free(t);                 // double free
const fuite = A.malloc(64); // jamais libéré
A.bilan("bilan");

console.log("");
console.log("— 2. tableau dynamique : doubler contre ajouter une case —");
for (const [nom, croissance] of [["doubler", (c) => c * 2], ["+ 1 case", (c) => c + 1]]) {
  const B = creerAllocateur();
  let capacite = 1, taille = 0;
  let bloc = B.malloc(capacite * 4);
  for (let i = 0; i < 1000; i++) {
    if (taille === capacite) { capacite = croissance(capacite); bloc = B.realloc(bloc, capacite * 4); }
    B.ecrire(bloc, taille, i);
    taille++;
  }
  console.log("   " + nom.padEnd(10) + " : " + String(B.recopies()).padStart(6) +
              " recopies pour 1000 insertions" +
              (nom === "doubler" ? "   (O(n) au total, donc O(1) amorti)" : "   (O(n²))"));
}

console.log("");
console.log("— 3. construire et libérer une liste chaînée —");
const C = creerAllocateur();
const VALEUR = 0, SUIVANT = 1;
let tete = 0;
for (const v of [3, 2, 1]) {
  const n = C.malloc(2 * 8);
  C.ecrire(n, VALEUR, v);
  C.ecrire(n, SUIVANT, tete);   // d'abord raccrocher la suite
  tete = n;                      // puis déplacer la tête
}
const vus = [];
for (let c = tete; c !== 0; c = C.lire(c, SUIVANT)) vus.push(C.lire(c, VALEUR));
console.log("   liste : " + vus.join(" -> "));

// L'ordre est imposé : lire le champ suivant AVANT de libérer la cellule,
// sinon on lit dans un bloc déjà rendu.
let c = tete;
while (c !== 0) {
  const suivant = C.lire(c, SUIVANT);
  C.free(c);
  c = suivant;
}
C.bilan("après libération");

Avant de commencer

• Le TP 7 : pointeurs et outils
• valgrind installé

Énoncé

1. Le tableau de taille inconnue — Écrivez une fonction qui lit tous les entiers d'un fichier dans un tableau alloué dynamiquement, en doublant la capacité quand elle est pleine. Testez sur 0, 1 et un million de valeurs.
2. L'allocation qui échoue — Demandez délibérément une allocation énorme et vérifiez le retour. Puis retirez le test et observez ce que fait le programme.
3. Mesurer une fuite — Écrivez une boucle qui alloue sans libérer et surveillez la mémoire du processus. Passez ensuite valgrind et lisez le résumé.
4. Les trois fautes — Provoquez successivement une double libération, une utilisation après libération, et une libération d'un pointeur non alloué. Notez ce que dit valgrind pour chacune.
5. realloc, et son piège — Utilisez realloc en réaffectant le résultat au pointeur d'origine, puis provoquez un échec d'allocation. Expliquez la fuite. Écrivez ensuite la forme correcte. Indice : Si realloc échoue, il renvoie NULL — et l'ancien bloc, lui, existe toujours.
6. Qui libère — Écrivez une fonction qui renvoie une chaîne allouée. Documentez le contrat, puis écrivez la fonction de libération qui va avec, et utilisez-la partout.
7. Au fil rouge — Faites lire à journal un fichier de taille quelconque, en allouant ce qu'il faut. Le programme doit se terminer avec zéro octet perdu selon valgrind.
8. Mesurer le coût — Comparez un million de petites allocations à une seule grande découpée à la main. Chronométrez les deux.

C'est réussi quand

• ✓ Votre lecteur gère un million de valeurs sans connaître la taille à l'avance
• ✓ valgrind annonce « All heap blocks were freed » sur votre fil rouge
• ✓ Vous savez écrire la forme correcte de realloc sans la relire

Correction

int *valeurs = NULL;
size_t n = 0, capacite = 0;

while (fscanf(f, "%d", &v) == 1) {
  if (n == capacite) {
      size_t nouvelle = capacite ? capacite * 2 : 16;
      int *tmp = realloc(valeurs, nouvelle * sizeof *valeurs);
      if (!tmp) { free(valeurs); return -1; }    /* forme CORRECTE */
      valeurs = tmp;
      capacite = nouvelle;
  }
  valeurs[n++] = v;
}

int *p = malloc(100000000000UL);
if (!p) { fprintf(stderr, "mémoire insuffisante\n"); return 1; }

sans le test :
p vaut NULL, puis *p = 0 → Segmentation fault
mais AILLEURS que là où l'allocation a échoué

valgrind --leak-check=full ./journal acces.log

==4412== HEAP SUMMARY:
==4412==   in use at exit: 40,960 bytes in 3 blocks
==4412==   total heap usage: 1,204 allocs, 1,201 frees
==4412== 
==4412== 40,960 bytes in 3 blocks are definitely lost
==4412==    at malloc (vg_replace_malloc.c:381)
==4412==    by lire_lignes (lecture.c:24)
==4412==    by main (main.c:12)

/* objectif : */
==4412== All heap blocks were freed -- no leaks are possible

free(p); free(p);        → Invalid free() / delete / delete[]
                          (le tas est corrompu : peut être EXPLOITABLE)

free(p); *p = 1;         → Invalid write of size 4
                          Address is 0 bytes inside a block of size 40 free'd

int t[10]; free(t);      → Invalid free(): pas une adresse du tas

/* la règle qui neutralise les deux premières */
free(p); p = NULL;       /* free(NULL) est autorisé et ne fait rien */

/* FAUX : si realloc échoue, l'ancien bloc est PERDU */
p = realloc(p, n);
if (!p) return -1;          /* fuite : l'ancien p n'existe plus nulle part */

/* CORRECT */
void *tmp = realloc(p, n);
if (!tmp) { free(p); return -1; }
p = tmp;

1 000 000 malloc(16) + free     : 0,094 s
1 malloc(16 Mo) découpé à la main : 0,004 s

malloc doit chercher un bloc libre, découper, mettre à jour
les métadonnées, et peut demander de la mémoire au noyau