Probleme – Un détecteur de fuites en trente lignes

1. L'interception. Le préprocesseur remplace du texte avant toute compilation : il suffit de faire de malloc une macro. Les macros __FILE__ et __LINE__, elles, valent le fichier et la ligne du point d'appel — c'est ce qui permet de nommer le coupable.

/* journal.h */
#ifndef JOURNAL_H
#define JOURNAL_H
#include <stddef.h>
void* journal_malloc(size_t n, const char* fichier, int ligne);
void  journal_free(void* p, const char* fichier, int ligne);
void  journal_bilan(void);
#define malloc(n) journal_malloc((n), __FILE__, __LINE__)
#define free(p)   journal_free((p), __FILE__, __LINE__)
#endif

Le fichier journal.c doit, lui, appeler les vrais malloc et free : il annule donc les macros par #undef après l'inclusion. C'est le seul endroit du programme qui le fasse.

2. Le module.

/* journal.c */
#include <stdio.h>
#include <stdlib.h>
#include "journal.h"
#undef malloc
#undef free

#define MAX 4096
static struct { void* p; size_t n; const char* fichier; int ligne; } vivants[MAX];
static int nb = 0;
static size_t pris = 0, rendu = 0;

void* journal_malloc(size_t n, const char* fichier, int ligne) {
    void* p = malloc(n);
    if (p == NULL) { return NULL; }
    assert(nb < MAX);
    vivants[nb].p = p;            vivants[nb].n = n;
    vivants[nb].fichier = fichier; vivants[nb].ligne = ligne;
    nb = nb + 1; pris = pris + n;
    return p;
}

void journal_free(void* p, const char* fichier, int ligne) {
    if (p == NULL) { return; }                 /* free(NULL) est LEGAL */
    for (int i = 0; i < nb; i = i + 1) {
        if (vivants[i].p == p) {
            rendu = rendu + vivants[i].n;
            vivants[i] = vivants[nb - 1];      /* on comble le trou par le dernier */
            nb = nb - 1;
            free(p);
            return;
        }
    }
    fprintf(stderr, "free d'un bloc inconnu en %s:%d (double liberation ?)\n",
            fichier, ligne);
}

Le journal_bilan parcourt vivants et imprime chaque bloc restant avec sa taille et son lieu de naissance.

Ce qu'il détecte en plus des fuites : la double libération, et gratuitement. Un free sur un pointeur absent de la table est soit un second free, soit un free sur une adresse qui n'a jamais été allouée — deux fautes du chapitre chap:langage-c, toutes deux invisibles à la compilation.

3. La mesure. Sur le programme

int* a = malloc(100 * sizeof(int));      /* ligne 5 */
int* b = malloc(50 * sizeof(int));       /* ligne 6 */
free(a);                                 /* ligne 7 */
for (int i = 0; i < 3; i = i + 1) {      /* ligne 8 */
    int* v = malloc(10 * sizeof(int)); v[0] = i;
}

le bilan affiche exactement :

pris 720 octets, rendu 400, fuite 320 octets en 4 blocs
  fuite de 200 octets alloues en fuite.c:6
  fuite de 40 octets alloues en fuite.c:8
  fuite de 40 octets alloues en fuite.c:8
  fuite de 40 octets alloues en fuite.c:8

Le diagnostic est complet : $200$ octets pour le b jamais libéré, et trois fois $40$ octets pour la boucle — et la ligne $8$ apparaît trois fois, ce qui dit que la fuite est dans une boucle, l'information la plus utile qui soit.

4. Ce qu'il ne voit pas, et c'est le vrai enseignement du problème :

• les débordements : écrire t[10] dans un bloc de $10$ cases ne passe par aucune de nos deux fonctions ;
• les utilisations après libération : après free, le bloc quitte notre table, et la lecture fautive ne nous est pas signalée ;
• les allocations faites par les bibliothèques, qui ne voient pas nos macros ;
• le coût : la recherche linéaire de journal_free rend une exécution avec $n$ allocations vivantes quadratique. Une table de hachage (chapitre chap:hachage) la ramènerait à $O(1)$ en moyenne.

Un outil comme valgrind ou -fsanitize=address n'a pas ces limites, parce qu'il n'instrumente pas la source mais les accès mémoire eux-mêmes. Notre dispositif reste utile pour ce qu'il apprend : le préprocesseur permet d'observer un programme sans le modifier, et il faut savoir exactement quelle partie de la vérité on observe.