La mémoire dynamique

Tous les tableaux rencontrés jusqu'ici ont une taille écrite dans le programme. C'est une contrainte sévère : un programme qui traite un fichier ne sait pas combien de lignes il contient, un serveur ne sait pas combien de connexions arriveront, et surdimensionner « au cas où » gaspille de la mémoire tout en restant faux le jour où le cas dépasse la prévision.

Le tas répond à ce besoin. On y demande des octets pendant l'exécution, on les garde aussi longtemps qu'on veut, et on les rend quand on a fini. Ce dernier point est le seul que le langage laisse entièrement à la charge de qui écrit : personne ne rend la mémoire à sa place, et personne ne signale l'oubli.

Demander, et rendre

Quatre choses se passent dans ce programme, et chacune a sa raison.

malloc prend un nombre d'octets, jamais un nombre d'éléments. D'où l'écriture combien * sizeof(int), qui reste juste sur toute machine.

Le résultat est vérifié contre NULL avant d'être employé. Une allocation peut échouer, et déréférencer le résultat sans l'avoir testé transforme un manque de mémoire en arrêt brutal.

Le bloc s'utilise exactement comme un tableau, crochets compris, parce qu'un tableau n'a jamais été autre chose qu'une adresse.

free rend les octets. À partir de cet instant, mesures ne désigne plus rien de valide, même si sa valeur numérique n'a pas changé.

Pile et tas, les deux mémoires

Sur la pile : les variables locales, dont la place est rendue automatiquement au retour de la fonction. Rapide, limitée, et sans aucune décision à prendre.
Sur le tas : ce qui doit survivre à la fonction qui l'a créé, ou dont la taille n'est connue qu'à l'exécution. Vaste, et entièrement à la charge du programme.
Le relevé sous chaque programme de ces pages donne les deux, en octets, avec le nombre de blocs alloués et le nombre encore actifs.

Ce qu'une fuite donne à voir

Le programme suivant ne provoque aucune erreur. Il alloue, il travaille, et il oublie de rendre.

Le relevé sous la sortie annonce trois blocs alloués, trois encore actifs, et nomme la ligne du malloc qui les a créés. C'est exactement ce que dirait un outil d'analyse sur un vrai programme.

À manipuler

Ajouter free(bloc); avant la fin du tour, relancer, et regarder le relevé : un seul bloc alloué au lieu de trois, aucun actif, et un tas de 400 octets au lieu de 1200. La place rendue a été réemployée par le tour suivant.
Remplacer ensuite 3 par 300 dans la boucle, sans le free : le tas finit par ne plus rien pouvoir servir, malloc rend NULL, et l'écriture qui suit s'arrête net sur un pointeur nul, faute de l'avoir testé. C'est ce que vit un programme qui fuit, à ceci près qu'il lui faut des heures pour en arriver là.

Ce qu'une fuite coûte vraiment

Pour un programme qui s'exécute en une seconde et s'arrête, une fuite ne coûte presque rien : le système reprend tout à la fin, quoi qu'il arrive.
Pour un programme qui tourne des mois, un serveur ou un système embarqué, la même fuite finit par consommer toute la mémoire de la machine. La gravité d'une fuite ne se lit pas dans le code qui fuit, elle se lit dans la durée de vie du programme et dans le nombre de fois où le code fautif est emprunté.

Les trois fautes, et leurs signes

Faute	Ce qui se passe hors de ces pages	Comment l'éviter
Fuite	la mémoire n'est jamais reprise, le programme grossit	un `free` pour chaque `malloc`, sur tous les chemins
Pointeur pendant	la lecture rend souvent la bonne valeur, jusqu'au jour où non	mettre le pointeur à `NULL` juste après le `free`
Double libération	corruption de la structure interne de l'allocateur, arrêt brutal plus tard	même règle : à `NULL` après le `free`, et `free(NULL)` ne fait rien

La deuxième ligne de ce tableau mérite l'insistance. Écrire bloc = NULL; après free(bloc); ne coûte rien, et transforme deux fautes indétectables en une faute que le premier test venu attrape.

Faire grandir un bloc

Quand la taille nécessaire n'est connue qu'au fur et à mesure, realloc agrandit un bloc en conservant son contenu.

Deux points méritent attention.

La capacité double au lieu d'augmenter d'un. Augmenter d'un à chaque ajout recopierait le bloc à chaque fois, ce qui rend le remplissage proportionnel au carré du nombre d'éléments ; en doublant, le coût total reste proportionnel au nombre d'éléments, parce que les agrandissements se raréfient à mesure que le bloc grossit.

realloc peut déplacer le bloc. C'est pourquoi son résultat est rangé dans valeurs : l'ancienne adresse ne vaut plus rien dès que la fonction a rendu une adresse différente. Garder une copie de l'ancien pointeur, et s'en servir ensuite, produit un pointeur pendant.

À manipuler

Remplacer capacite = capacite * 2; par capacite = capacite + 1; et suivre les lignes annonçant la capacité : il y en a bien plus, et chacune représente une recopie complète du bloc.
Porter ensuite la boucle à mille valeurs avec l'une puis l'autre version : la différence n'est plus une question de style, c'est un facteur de plusieurs centaines sur le travail effectué.

À calculer soi-même

Une allocation se compte en octets, et le compte se fait avant l'appel.

Ce qu'on demande au tas

1.
Combien d'octets demande malloc(50 * sizeof(int)) ?
2.
Combien d'octets faut-il demander pour 200 caractères et leur zéro final ?
3.
Un tableau dynamique part d'une capacité de 2 et double à chaque fois qu'il est plein. Quelle capacité a-t-il après 5 doublements ?
4.
Combien de doublements faut-il pour dépasser 1000 éléments en partant de 2 ?
5.
Une fuite de 1 kibioctet par seconde dans un serveur : combien de mébioctets perdus en une journée ?
6.
Un programme fait 1000 malloc et 997 free. Combien de blocs fuient ?
7.
Une fonction alloue un bloc et rend son adresse, et ses appelants oublient le free une fois sur dix. Sur 10000 appels, combien de blocs fuient ?

Le dernier résultat dit où se trouve la difficulté réelle : ce n'est pas d'écrire free, c'est de savoir qui doit l'écrire. Une fonction qui alloue et rend un bloc transfère cette charge à son appelant, et cette obligation ne se lit nulle part dans le langage. Elle s'écrit dans un commentaire, ou elle se perd.

Vérification

Vérification rapideon peut se reprendre

1.Que prend malloc en argument ?

2.Que faut-il faire du résultat de malloc avant de s'en servir ?

3.Quel est le signe d'une fuite dans les programmes de ces pages ?

4.Pourquoi mettre un pointeur à NULL après un free ?

5.Pourquoi doubler la capacité d'un tableau dynamique plutôt que l'augmenter d'un ?

Exercices type

Qui doit libérer un bloc alloué par une fonction et rendu à son appelant ?

L'appelant, et rien dans le langage ne le dit. Cette obligation s'appelle la propriété du bloc, et elle se transmet avec l'adresse sans qu'aucun mécanisme ne la porte.

D'où la convention qu'appliquent les bibliothèques sérieuses : la documentation de toute fonction qui rend un pointeur dit explicitement si l'appelant doit le libérer, et souvent la bibliothèque fournit la fonction de libération correspondante plutôt que de laisser employer free directement.

Les langages plus récents ont tous tenté de rendre cette obligation lisible dans le code lui-même, par un ramasse-miettes ou par un système de propriété vérifié à la compilation.

Un programme alloue 1000 blocs de 1 kibioctet et les libère tous. Le tas retrouve-t-il son état initial ?

La mémoire est disponible à nouveau, mais pas forcément d'un seul tenant. Les allocations et libérations successives laissent des trous entre les blocs restants, et cette fragmentation peut faire échouer une demande d'un mébioctet d'un seul tenant alors que la mémoire libre totale est bien supérieure.

C'est une des raisons pour lesquelles les systèmes embarqués de longue durée évitent l'allocation dynamique, ou l'emploient au démarrage uniquement, puis réutilisent des blocs de taille fixe pris dans une réserve préparée à l'avance.

Un pointeur est libéré dans une branche d'un if, et pas dans l'autre. Comment traiter ce cas ?

En ramenant la libération à un seul endroit, à la fin de la fonction, et en n'employant return qu'après ce point. C'est le motif le plus répandu en C : un bloc de nettoyage unique en fin de fonction, vers lequel tous les chemins convergent.

Le contrôle qui vaut la peine consiste à relire la fonction en cherchant tous les return, y compris ceux qui traitent une erreur, et à vérifier que chacun passe par la libération. Les chemins d'erreur sont ceux qui fuient, précisément parce qu'ils sont rarement empruntés et jamais testés.

La méthode

Demander en octets : n * sizeof(type), jamais un nombre d'éléments.
Tester contre NULL immédiatement après l'allocation.
Écrire le free en même temps que le malloc, avant d'écrire le code qui se trouve entre les deux.
Mettre le pointeur à NULL juste après la libération.
Ranger le résultat de realloc dans le pointeur lui-même, et considérer l'ancienne adresse comme périmée.

Synthèse

Le tas porte ce dont la taille n'est connue qu'à l'exécution, ou ce qui doit survivre à la fonction qui l'a créé.
malloc prend un nombre d'octets et peut rendre NULL : le résultat se teste avant tout usage.
Une fuite n'est pas une erreur d'exécution. Sa gravité dépend de la durée de vie du programme et du nombre de fois où le code fautif est emprunté.
Pointeur pendant et double libération se neutralisent d'une seule habitude : mettre le pointeur à NULL après le free.
realloc conserve le contenu et peut déplacer le bloc : son résultat remplace l'ancien pointeur, qui ne vaut plus rien.

Et ensuite

Le tas sait maintenant fournir de la place à la demande, et il ne sert vraiment qu'à partir du moment où l'on y range autre chose que des nombres. Les structures rassemblent plusieurs valeurs sous un seul nom, et ouvrent tout ce qui se construit avec des pointeurs.