Contexte

La famille des langages C traîne un héritage qui, selon le point de vue, a été applaudi autant que maudit: la gestion manuelle de la mémoire. Le modèle de calcul du langage C est simple: quand on alloue de la mémoire hors de la pile de données (dans la région du tas du processus), on est responsable de désallouer (libérer) cette mémoire. Si on oublie cette allocation, le processus devient incapable de réutiliser cette région de la mémoire. Ce type d’erreur est appelé fuite de mémoire. Aucun ramasse-miettes ne viendra se sauver si on épuise la mémoire disponible en répétant cette erreur.

Les textes d’introduction aux langages C et C++ masquent la fréquence réelle des fuites de mémoire. Ces tutoriels allouent et libèrent quelque mémoire nécessaire dans une même fonction. Dans du vrai code, on alloue de la mémoire sur le tas de manière à communiquer des données d’une fonction à une autre, souvent distante dans le temps et la position dans le code. À mesure que le programme est développé dans un contexte de collaboration, les chemins d’exécutions sûrs et testés contre les fuites deviennent fourchus, les conventions qu’ils modélisent deviennent obscures. Les fuites de mémoire, dans la réalité, surviennent dans les cas limites, résultent d’une refactorisation du code, découlent d’un manque de communication entre collaborateurs, etc. Les fuites de mémoire sont causées par la complexité d’implantation, même lorsque cette complexité est activement minimisée.

Nous proposons ici une méthode efficace et simple pour détecter et résoudre les fuites de mémoire, qui a bien marché pour nous. Cette méthode est mise en oeuvre pour des compilations de développement du programme, et ses surcharges sont (presque) entièrement retirées du code de production. Cette approche n’est vraisemablablement pas originale, elle est en fait largement triviale. Elle nous apparaît cependant trop utile pour la garder sous silence, aussi le reste de cet article en présente la motivation et l’implantation.

Pointer du doigt, c’est impoli (mais nécessaire)

Notre approche se résume à répondre à la question: “Qui est responsable pour libérer cette mémoire?” À un certain endroit dans le programme, la mémoire se trouve allouée; elle est ensuite utilisée par d’autres routines, et finalement elle doit être libérée. Donc, à partir du moment où la mémoire est allouée, on doit choisir une fonction responsable pour la libérer: cette fonction est le propriétaire de la région allouée. Cela peut être la fonction qui a invoqué malloc. Alternativement, ce titre de propriété peut être transféré à une fonction appelée par celle qui a alloué, ou encore à un appelant de cette fonction. D’autres fonctions peuvent se voir passer un pointeur vers cette région de mémoire, mais pas la propriété: elles ne sont que des usagers de cette région; elles y lisent ou y écrivent, mais elles ne sont pas censées la libérer.

Dans ce cadre de travail, une fuite de mémoire est une fonction qui a négligé son rôle de propriétaire. Déboguer un tel problème revient à comprendre la chaîne de transfert de la propriété entre les fonctions, de manière à comprendre qui s’est planté. Ces chaînes sont difficiles à étiqueter durant le développement, car elles changent fréquemment et l’étiquetage est parallèle au code (il s’agit d’une duplication d’un comportement attendu). Ainsi, si le programme et l’étiquetage deviennent désynchronisés, ce dernier nuit davantage qu’il n’aide au déboguage. Plutôt, supposons que le pauvre stagiaire qui exécutera le déboguage devrait être en mesure de retracer la chaîne de transferts de propriété sans trop de problème, du moment qu’il peut savoir où cette chaîne commence. Connaître le nombre d’octets perdus par fuite, ou même l’adresse et la longueur des régions perdues, ne nous aide pas énormément. Cependant, savoir où dans le code telle région a été allouée résout 80% du problème. Heureusement, les compilateurs C procurent des outils pratiques pour assister ce suivi.

En bref: on veut pouvoir blamer le code qui alloue sur le tas de ne pas s’être assuré que sa mémoire soit libérée.

Le dictionnaire d’allocation

Premièrement, nous allons emballer l’allocateur de notre choix dans une fonction de notre crû. L’exemple qui suit utilise la routine standard malloc, mais on pourrait tout aussi bien utiliser un autre allocateur.

#ifdef MEMORY_LEAK_TRACKING
typedef struct _allocPrefix_
{
    unsigned long from;
    size_t size;
} allocPrefix;
#endif

void* my_mallocFrom( size_t size, unsigned long from )
{
#ifdef MEMORY_LEAK_TRACKING
    allocPrefix* prefix = (allocPrefix*)malloc( size + sizeof( allocPrefix ) );
    if( NULL == prefix )
    {
        return NULL;
    }
    prefix->from = from;
    prefix->size = size;
    g_allocDict[ from % ALLOC_DICT_LEN ] += size;
    return prefix + 1;
#else
    return malloc( size );
#endif
}

Bien sûr, pour effectuer le suivi, on doit compiler en définissant la macro MEMORY_LEAK_TRACKING (soit dans le code, soit via une option du compilateur). On utilise ici un tableau global nommé g_allocDict, déclaré quelque part avant cette fonction:

#ifdef MEMORY_LEAK_TRACKING
#define ALLOC_DICT_LEN   (1 << 20);
unsigned long g_allocDict[ ALLOC_DICT_LEN ] = { 0 };
#endif

Ceci est le dictionnaire d’allocation: il suit combien d’octets ont été alloués à chaque endroit possible du code du projet. Cet endroit est aussi stocké avant la région exigé par l’appelant de my_mallocFrom, avec la taille de cette région. On doit aussi emballer l’opération réciproque de malloc pour libérer la mémoire allouée:

void my_free( void* ptr )
{
#ifdef MEMORY_LEAK_TRACKING
    allocPrefix* prefix = (allocPrefix*)( ptr - sizeof( allocPrefix ) );
    g_allocDict[ prefix->from % ALLOC_DICT_LEN ] -= prefix->size;
    free( prefix );
#else
    free( ptr );
#endif
}

Utiliser le nouvel allocateur

À présent, partout dans le code où on alloue de la mémoire sur le tas, on remplace l’usage de malloc par my_mallocFrom, ainsi que free par my_free. Pour chaque telle allocation, on utilise un identificateur numérique unique comme second paramètre. Évidemment, faire ceci à la main est fastidieux – personne ne veut maintenir une liste de tous les identificateurs utilisés.

Heureusement, le compilateur peut automatiser une grande part de cette maintenance, via l’usage de macros. Le compilateur offre au programmeur les macros prédéfinies __FILE__ et __LINE__ durant la compilation, qu’on peut utiliser via d’autres macros. Dans ce cas, on désire générer des identificateurs numériques uniques associés à la position d’une allocation dans le code du programme. La macro __FILE__ n’est pas facile à utiliser en ce sens, mais assurément __LINE__ peut être utile. En supposant qu’on puisse associer un identificateur numérique unique à chaque fichier C du projet (une tâche simple, ou du moins, pas aussi fastidieuse que de maintenir des identificateurs de position dans le code), on peut le combiner avec __LINE__ pour former l’identificateur d’intérêt:

#define MEM_ALLOC_TAG        ( ( ( UNIQUE_FILE_ID & 0xff ) << 12 ) | ( __LINE__ & 0xfff ) )
#define my_malloc( size )    my_mallocFrom( (size), MEM_ALLOC_TAG )

Grâce à l’évaluation tardive des macros par le compilateur C, UNIQUE_FILE_ID est résolu à sa plus récente définition (laquelle devrait apparaître quelque part au début de chaque fichier de code C du project), et __LINE__ au numéro de la ligne de code courante, chaque fois que my_malloc est rencontré par le compilateur.

La définition de MEM_ALLOC_TAG ci-haut est liée à celle de ALLOC_DIC_LEN vue précédemment. Le schéma décrit génère des identificateurs de 20 bits: les 8 bits de poids fort sont réservés pour l’identificateur de fichier, alors que les 12 bits de poids faible sont réservés au numéro de ligne. On s’attend donc à ce que le projet contienne, au plus, 256 fichiers avec l’extension .c, chacun d’entre eux contenant 4096 lignes ou moins. Le dépassement de ces limites ne plantera pas le programme, mais peut causer des surprises dans le rapport des positions dans le code (par exemple: une fuite de la mémoire allouée à la ligne 5000 serait rapportée comme ayant été causée par la ligne 904). La dictionnaire d’allocation qui résulte de ce schéma est stocké sur 4~MB. C’est plutôt grand, mais certainement envisageable sur des ordinateurs et appareils mobiles modernes.

Le suivi des fuites de mémoire

Si le programme ne comporte aucune fuite, toute la mémoire allouée sur le tas est libérée en temps convenable; lorsque le programme se termine, toutes les entrées du dictionnaire d’allocation sont nulles. Vérifions donc le contenu du dictionnaire d’allocation juste avant de terminer, en invoquant la fonction suivante:

void listAllocDict()
{
#ifdef MEMORY_LEAK_TRACKING
    unsigned long i, file_id, line;

    for( i = 0; i < ALLOC_DICT_LEN; ++i )
    {
        if( 0 < g_allocDict[ i ] )
        {
            file_id = ( i >> 12 );
            line = ( i & 0xfff );
            printf(
                    "File %03u, line %03u: %lu bytes\n",
                    file_id,
                    line,
                    g_allocDict[ i ]
                    );
        }
    }
#endif
}

Transfert de la propriété

Supposons qu’on implante une structure de données basée sur l’allocation sur le tas, comme un tableau auto-extensible, un arbre ou une liste liée. Les allocations sont cachées dans les routines d’implantation de la structure. Ainsi, par défaut, les positions identifiées dans le dictionnaire correspondent pointent vers le code de construction et de maintenance de la structure. Supposons donc que ce code soit bien écrit et qu’il ne fuie pas de mémoire. Cependant, si le code qui utilise cette structure de données l’utilise mal, il pourrait laisser fuire de la mémoire allouée indirectement pour cette structure. Dans ce cas, the rapport de suivi généré par listAllocDict rapportera des fuites liées aux positions dans le code de la structure de données. Si ce code est utilisé par une seule routine dans le projet, on peut remonter vers le code usager erroné. Cependant, s’il s’agit d’une structure de données abstraite utilisée par plusieurs autres routines, le rapport de suivi ne sert plus à rien.

La clef de ce problème consiste à reconnaître que si le code de la structure de données est fiable, la propriété des allocations est effectivement transférée à ses usagers. Les allocations au sein du code de construction de la structure devraient donc être plutôt marquées par la position du code exigeant la création de cette instance de la structure. Voici un exemple. Considérons qu’on crée un tampon auto-extensible d’octets:

typedef struct _elasticBuffer_
{
    void*  bytes;
    size_t size;
} elasticBuffer;

int elasticBuffer_create( elasticBuffer* eb, size_t init_size )
{
    if( init_size < 1 )
    {
        return 0;
    }
    eb->bytes = my_malloc( init_size );
    if( NULL == eb->bytes )
    {
        return 0;
    }
    eb->bytes = init_size;
    return 1;
}

void elasticBuffer_free( elasticBuffer* eb )
{
    if( NULL != eb->bytes )
    {
        free( eb->bytes );
        eb->bytes = NULL;
    }
    eb->size = 0;
}

Si on crée l’un de ces tampons (via elasticBuffer_create) mais qu’on omet de le libérer (via elasticBuffer_free), la fuite sera comptée pour la ligne dans elasticBuffer_create où my_malloc est appelée. On devrait plutôt transférer la propriété de cette allocation à l’appelant de elasticBuffer_create. Ré-écrivons cette fonction:

#define elasticBuffer_create( eb, init_size ) elasticBuffer_create_from( (eb), (init_size), MEM_ALLOC_TAG )
int elasticBuffer_create_from(
        elasticBuffer* eb,
        size_t init_size,
        unsigned long from )
{
    if( init_size < 1 )
    {
        return 0;
    }
    eb->bytes = my_mallocFrom( init_size, from );
    if( NULL == eb->bytes )
    {
        return 0;
    }
    eb->bytes = init_size;
    return 1;
}

En remplaçant my_malloc avec my_mallocFrom, on réalise ce transfert de responsabilité. Si l’appelant omet d’invoquer elasticBuffer_free pour libérer son instance du tampon, tous les octets compilés pour le tampon seront blamés sur cet appelant.

Supposons à présent que le tampon doive être étendu au-delà de sa taille initiale. On implante cette extension dans une fonction de réallocation du tampon:

int elasticBuffer_realloc( elasticBuffer* eb, size_t new_size )
{
    if( new_size > eb->size )
    {
        void* new_bytes = my_malloc( new_size );
        if( NULL == new_bytes )
        {
            return 0;
        }
        memcpy( new_bytes, eb->bytes, eb->size );
        my_free( eb->bytes );
        eb->bytes = new_bytes;
        eb->size = new_size;
    }

    return 1;
}

Ici encore, si le tampon n’est pas libéré avec elasticBuffer_free après qu’une telle réallocation se soit produite, la fuite sera blamée sur elasticBuffer_realloc. Pour éviter cette situation, le tampon devrait stocker la position de son instantiation originale. De ce fait, tous les octets alloués pour ce tampon seront blamés à l’appelant s’ils sont perdus. Ré-écrivons les données et les routines pertinentes:

typedef struct _elasticBuffer_
{
    void*         bytes;
    size_t        size;
    unsigned long from;
} elasticBuffer;

#define elasticBuffer_create( eb, init_size ) elasticBuffer_create_from( (eb), (init_size), MEM_ALLOC_TAG )
int elasticBuffer_create_from(
        elasticBuffer* eb,
        size_t init_size,
        unsigned long from )
{
    if( init_size < 1 )
    {
        return 0;
    }
    eb->bytes = my_mallocFrom( init_size, from );
    if( NULL == eb->bytes )
    {
        return 0;
    }
    eb->bytes = init_size;
    eb->from = from;
    return 1;
}

int elasticBuffer_realloc( elasticBuffer* eb, size_t new_size )
{
    if( new_size > eb->size )
    {
        void* new_bytes = my_mallocFrom( new_size, eb->from );
        if( NULL == new_bytes )
        {
            return 0;
        }
        memcpy( new_bytes, eb->bytes, eb->size );
        my_free( eb->bytes );
        eb->bytes = new_bytes;
        eb->size = new_size;
    }

    return 1;
}

Limites et mises en garde

Le principal inconvénient de cette approche consiste en la petite surcharge imposée même sur le code compilé sans le dictionnaire d’allocation (MEMORY_LEAK_TRACKING non définie). Dans ce cas, les identificateurs de position de code demeurent dans la liste de paramètres des fonctions qui devraient la faire suivre; ils demeurent aussi dans les structures qui doivent les transporter à travers leur cycle d’existence, comme le elasticBuffer esquissé précédemment. Passer un mot mémoire en paramètre n’est pas une énorme surcharge, sauf peut-être dans la boucle interne de processus dont la performance est étroitement liée au processeur. Un profilage rigoureux est de mise avant de pointer cette surcharge comme la cause d’un programme trop lent.

L’autre limite en regard de librairies spécialisées comme valgrind est que seul le code appartenant à son propre projet peut être ainsi surveillé. Les librairies binaires contre lesquelles on lie le programme ne sont pas compilées avec l’allocateur emballé. Les librairies libres peuvent être recompilées, mais elles doivent être modifiées pour utiliser l’allocateur modifié, aussi deviennent-elles alors sous la responsabilité de maintenance par le programmeur (ick!).

Exercices pour le lecteur

1. La librairie standard du langage C offre la fonction realloc comme alternative et supplément à malloc. Cette fonction peut soit étendre une région de mémoire précédemment allouée avec malloc, ou encore allouer une région distincte pour accomoder une taille démandée. Cette fonction devrait-elle être emballée, comme on a emballé malloc? Contre quel identificateur de position dans le code devrait-on compter une allocation commise par realloc?
2. Le dictionnaire d’allocation est très grand, mais aussi très creux: même si on alloue de la mémoire sur le tas dans plusieurs endroits dans un projet, on tend à utiliser moins de 1% d’un dictionnaire de 4 MB. Dérivez un autre schéma d’adressage du dictionnaire permettant d’en limiter la taille à 64 KB (donc 2^14 éléments d’un mot, ou encore 2^15 éléments d’un demi-mot). Vraisemblablement, des scripts d’analyse du code seront nécessaires pour faire correspondre les identificateurs aux positions dans le code du projet.
3. Les fuites de mémoire sont d’autant plus pernicieuses lorsqu’on implante un programme à fils d’exécution multiples. Dans de tels programmes, on alloue fréquemment de la mémoire dans certains fils, qu’on ne libère que dans d’autres. Modifiez le code ci-haut pour éviter la corruption du dictionnaire d’allocation causée par des conditions de compétition.
4. Implantez des macros qui permettraient de débarasser le programme de tout code de suivi des fuites de mémoire lorsque la macro MEMORY_LEAK_TRACKING n’est pas définie. Minimisez le code répétitif.