Skip to content
Computer Internals

Niveau 2 · Chapitre 2.6

Structures, malloc et le tas

Les structures et l’opérateur ->, pourquoi un programme a besoin de mémoire qui survit à un appel de fonction, et comment fonctionnent vraiment malloc et free : en-têtes de blocs, classes de tailles, listes libres et réutilisation de la mémoire libérée — mesurés sur la glibc —, puis les fuites, l’utilisation après libération et la double libération, et comment d’autres langages les évitent.

Les variables locales vivent sur la pile et meurent au retour de leur fonction ; les globales vivent toujours, mais ont une taille fixe, décidée à la compilation. Les vrais programmes ont besoin d’une troisième sorte de mémoire : des blocs dont la taille n’est connue qu’à l’exécution, et dont la durée de vie est décidée par le programme — créés dans une fonction, utilisés dans d’autres, libérés quand on n’en a plus besoin. C’est le tas (heap), et en C on le gère à la main avec malloc et free.

Les données du tas sont en général des structures, alors commençons par elles.

Les structures et ->

Une structure regroupe des champs nommés en un seul objet. Le chapitre sur les variables a montré comment le compilateur dispose ses champs, avec du remplissage pour l’alignement. Pour la machine, un champ n’est qu’un décalage : p.x, ce sont « les 4 octets au décalage 4 depuis le début de p ».

On manipule presque toujours les structures par pointeur, et le C a un opérateur pour cela : p->x signifie (*p).x, « le champ x de la structure pointée par p ». Au niveau de la machine, c’est une seule instruction avec déplacement, comme mov eax, DWORD PTR [rax+4] : le mode d’adressage base + déplacement existe exactement pour cela.

malloc et free

void *malloc(size_t size);   // un bloc d’au moins size octets, ou NULL
void  free(void *p);         // le rendre

malloc renvoie un pointeur vers un nouveau bloc que personne d’autre n’utilise. Le bloc reste valide jusqu’à ce qu’on le passe à free — quelle que soit la fonction où l’on se trouve. calloc(n, size) remplit en plus le bloc de zéros, et realloc le redimensionne, quitte à le déplacer. Les octets renvoyés par malloc ne sont pas effacés : ils contiennent ce qui s’y trouvait avant.

L’usage classique est une structure de données qui grandit pendant l’exécution, comme une liste chaînée : chaque nœud est une structure allouée séparément, qui contient un pointeur vers le suivant.

Live · Une liste chaînée sur le tas

À essayer : Appuyez sur Step pour exécuter une instruction, Run pour animer ou Continue pour aller au bout ; les boutons L2 à L7 changent de niveau, vers le bas ou le haut.

C source — click a line number for a breakpoint
  1. struct Node {
  2. int value;
  3. struct Node *next;
  4. };
  6. struct Node *push(struct Node *head, int value) {
  7. struct Node *n = malloc(sizeof(struct Node));
  8. n->value = value;
  9. n->next = head;
  10. return n;
  11. }
  13. int main() {
  14. struct Node *list = 0;
  15. list = push(list, 3);
  16. list = push(list, 2);
  17. list = push(list, 1);
  19. int sum = 0;
  20. for (struct Node *p = list; p; p = p->next)
  21. sum = sum * 10 + p->value;
  23. while (list) {
  24. struct Node *next = list->next;
  25. free(list);
  26. list = next;
  27. }
  28. return sum;
  29. }
step 0
Loading emulator…
Your program as you wrote it: the current line, its variables by name, and its output.

Il renvoie 123 : la liste se lit 1 → 2 → 3, puisque chaque push ajoute en tête. Contrairement au pointeur pendant du chapitre précédent, le nœud renvoyé par push reste valide après le retour de push : il vit sur le tas, pas dans le cadre de push. Regardez le panneau du tas pendant la création des nœuds, puis leur libération un à un à la fin.

Ce que fait vraiment malloc

malloc n’est pas un appel système. C’est une fonction de bibliothèque — dans la glibc sous Linux — qui gère une grande zone de mémoire obtenue du système d’exploitation et la découpe en blocs. Le malloc du simulateur suit les mêmes règles que celui de la glibc sur Linux 64 bits, donc les chiffres ci-dessous sont les mêmes dans les deux.

Chaque bloc a un en-tête. L’allocateur range la taille de chaque bloc dans les 8 octets situés juste avant l’adresse renvoyée. Un bloc et son en-tête forment un chunk. Sur la glibc 64 bits, la taille des chunks est un multiple de 16, et le plus petit fait 32 octets. Mesuré avec la glibc 2.36 :

DemandeTaille du chunkChamp de taille avant le blocOctets utilisables
malloc(1)320x2124
malloc(24)320x2124
malloc(25)480x3140

Le champ de taille est la taille du chunk avec le bit de poids faible à 1 : comme les tailles sont des multiples de 16, les bits de poids faible sont libres pour porter des indicateurs, et le bit 0 note que le chunk précédent est utilisé. Demander 1 octet en consomme 32. Ce gaspillage à l’intérieur d’un bloc est la fragmentation interne, le prix d’une allocation rapide et alignée. Dans la démo de liste ci-dessus, le panneau du tas montre l’en-tête de chaque nœud, 0x21, devant ses 16 octets.

Les chunks libérés vont dans des listes libres, et sont réutilisés. free ne rend pas la mémoire au système. Il place le chunk dans une liste de chunks libres, classés par taille dans des bins, et le prochain malloc d’une taille qui convient le reprend. Les listes les plus rapides de la glibc, le tcache propre à chaque thread, fonctionnent en dernier entré, premier sorti : libérez deux blocs de 8 octets et les deux malloc(8) suivants les renvoient dans l’ordre inverse. C’est mesuré sur la glibc, et c’est aussi ce que fait le simulateur.

Le tas grandit en demandant au système. Quand aucun chunk libre ne convient, la glibc étend la zone du tas, traditionnellement avec l’appel système brk, qui déplace la fin du segment de données. Les grosses demandes — 128 Kio et plus par défaut — contournent complètement le tas et reçoivent leurs propres pages de mmap. Sur la machine de test, un malloc(10) a renvoyé une adresse voisine des données du programme, et un malloc(200000) une adresse très éloignée, dans la zone où sont projetées les bibliothèques partagées. Libérer un bloc obtenu par mmap le rend immédiatement au système.

Le problème général est celui que décrit Tanenbaum pour placer des segments en mémoire : quel trou libre choisir pour un nouveau bloc. First fit prend le premier trou assez grand, best fit le plus petit. Les deux découpent les trous et laissent de petits restes inutilisables, la fragmentation externe, que les allocateurs combattent en fusionnant les chunks libres voisins en plus grands. Les allocateurs modernes y ajoutent des classes de tailles et des caches par thread, car un vrai programme appelle malloc des millions de fois par seconde, et il doit être rapide.

Les bugs du tas

Le tas donne un contrôle total, et une responsabilité totale. Trois erreurs sont classiques.

Les fuites. Un bloc jamais libéré reste alloué jusqu’à la fin du processus. Une fuite isolée est sans conséquence ; une fuite dans une boucle, dans un serveur qui tourne des mois, finit par épuiser la mémoire. Des outils comme Valgrind et LeakSanitizer (-fsanitize=address) listent les blocs encore alloués à la sortie, et leur provenance.

L’utilisation après libération (use after free). Après free(p), p contient toujours la même adresse — rien ne l’efface —, mais la mémoire appartient désormais à l’allocateur, qui la donnera au prochain malloc de cette taille :

Live · Utilisation après libération

À essayer : Appuyez sur Step pour exécuter une instruction, Run pour animer ou Continue pour aller au bout ; les boutons L2 à L7 changent de niveau, vers le bas ou le haut.

C source — click a line number for a breakpoint
  1. struct Account {
  2. int id;
  3. int balance;
  4. };
  6. int main() {
  7. struct Account *a = malloc(sizeof(struct Account));
  8. a->id = 1;
  9. a->balance = 100;
  10. free(a);
  12. struct Account *b = malloc(sizeof(struct Account));
  13. b->id = 2;
  14. b->balance = 999;
  16. return a->balance;
  17. }
step 0
Loading emulator…
Your program as you wrote it: the current line, its variables by name, and its output.

Il renvoie 999. b a reçu le même chunk que a, donc lire a->balance, c’est lire le compte de b. Le programme ne plante pas ; il mélange silencieusement deux objets. C’est pourquoi l’utilisation après libération est aujourd’hui l’une des familles de failles les plus exploitées dans les navigateurs et les systèmes d’exploitation : si un attaquant contrôle ce qui est alloué dans le chunk libéré, il contrôle ce que voit le pointeur périmé. Mettre les pointeurs à NULL après free transforme les utilisations ultérieures en plantage net.

La double libération (double free). Libérer deux fois le même bloc le place deux fois dans la liste libre, si bien que deux futurs malloc renverraient la même mémoire. La glibc détecte le cas simple : le programme est arrêté avec free(): double free detected in tcache 2, et meurt avec le code de sortie 134, soit SIGABRT. Le simulateur s’arrête avec le même diagnostic.

Écrire au-delà de la fin d’un bloc du tas est la version tas du débordement de pile du chapitre sur les pointeurs : cela écrase l’en-tête et les données du chunk suivant. Les attaques sur le tas ont longtemps visé les métadonnées de l’allocateur lui-même. Les allocateurs répondent par des contrôles d’intégrité et, depuis la glibc 2.32, par le « safe-linking », qui brouille les pointeurs rangés dans les chunks libres.

D’autres façons de gérer la mémoire

Gérer malloc et free à la main est rapide et prévisible, mais la durée de vie de chaque bloc est l’affaire du programmeur. D’autres langages la confient à quelqu’un d’autre :

  • Le ramasse-miettes (garbage collector : Java, Go, JavaScript, Python, C#) : l’environnement d’exécution trouve les blocs que plus rien ne désigne et les libère. Plus de blocs oubliés ni d’utilisation après libération, au prix de travail à l’exécution et de pauses. C’est le sujet du chapitre sur les machines virtuelles à bytecode et le ramasse-miettes.
  • La possession (ownership : le RAII et les pointeurs intelligents du C++, Rust) : chaque bloc a un propriétaire, et le compilateur insère le free quand le propriétaire sort de sa portée. Le compilateur de Rust refuse en plus les programmes qui pourraient utiliser un bloc après sa libération.
  • Les arènes : allouer de nombreux objets dans un grand bloc et les libérer tous d’un coup, comme le font souvent les compilateurs et les moteurs de jeu pour les données d’une image ou d’une requête.

Toutes ces approches reposent encore, en dessous, sur quelque chose comme malloc pour obtenir de la mémoire du système et la découper.

À retenir

  • Les champs d’une structure sont des décalages ; p->x vaut (*p).x, un chargement avec déplacement.
  • Le tas contient des blocs dont la taille est connue à l’exécution et dont le programme décide la durée de vie : malloc en donne un, free le rend.
  • malloc est une bibliothèque qui découpe la mémoire du système en chunks, chacun précédé d’un en-tête de taille : 32 octets minimum sur la glibc 64 bits, champ de taille 0x21.
  • free place les chunks dans des listes libres (le tcache de la glibc est en dernier entré, premier sorti), et le prochain malloc de cette taille les réutilise. Les gros blocs viennent de mmap.
  • Les fuites, l’utilisation après libération (l’ancien pointeur voit le nouvel objet) et la double libération (la glibc interrompt le programme) sont les bugs classiques du tas.
  • Le ramasse-miettes, la possession et les arènes sont les alternatives à la gestion manuelle des durées de vie.

Dans ce niveau

  1. 2.1Langages compilés, interprétés et compilés à la volée (JIT)
  2. 2.2Du code source au binaire qui s’exécute
  3. 2.3Variables, types et disposition en mémoire
  4. 2.4Pointeurs et tableaux
  5. 2.5Fonctions, appels et la pile
  6. 2.6Structures, malloc et le tas
  7. 2.7Flot de contrôle : if, boucles, switch
  8. 2.8Machines virtuelles à bytecode et ramasse-miettes