Pile et tas en C : durées de vie, pointeurs pendouillants et lequel choisir

Toute variable d'un programme C vit quelque part, et ce où détermine deux choses que vous ne pourrez pas changer ensuite : combien de temps elle survit, et quelle quantité vous pouvez en avoir. Le C vous donne trois régions de stockage, et mal choisir produit soit un plantage, soit une fuite. Cette page les expose et montre le bug classique qui vient d'une mauvaise gestion des durées de vie.

Les trois régions

  adresses hautes
  +---------------------------+
  |  pile                     |  locales, parametres, adresses de retour
  |    croit vers le bas  |   |  liberees automatiquement au retour
  |                       v   |
  +---------------------------+
  |         (espace inutilise)|
  +---------------------------+
  |                       ^   |
  |    croit vers le haut |   |
  |  tas                      |  blocs malloc / calloc / realloc
  +---------------------------+  liberes uniquement par free()
  |  donnees statiques/global |  globales et statiques, toute l'execution
  +---------------------------+
  |  code (text)              |  le code machine, en lecture seule
  +---------------------------+
  adresses basses

• Le stockage automatique (la pile) contient les paramètres de fonction et les locales non static. Un bloc de pile est réservé à l'entrée d'une fonction et rendu au retour. La taille est fixée à la compilation.
• Le stockage dynamique (le tas) contient tout ce qui vient de malloc, calloc et realloc. La taille est décidée à l'exécution ; la durée de vie ne se termine qu'au free.
• Le stockage statique contient les globales et tout ce qui est déclaré static. Il existe pendant toute l'exécution du programme et est initialisé à zéro avant le démarrage de main.

Les adresses du schéma représentent l'agencement habituel, pas une garantie - la norme décrit les durées de vie, pas la disposition.

Le stockage automatique en action

#include <stdio.h>

void demo(void) {
    int local = 42;             /* cree ici */
    int table[4] = {1, 2, 3, 4};

    printf("local = %d, table[0] = %d\n", local, table[0]);
}                               /* les deux liberes ici */

int main(void) {
    demo();
    demo();
    return 0;
}

Chaque appel à demo obtient un local neuf et une table neuve. Rien n'est libéré à la main, rien ne peut fuir, et l'allocation coûte une seule instruction qui déplace le pointeur de pile. C'est pourquoi les locales ordinaires devraient être votre choix par défaut : c'est le stockage le plus rapide et le plus sûr du C.

Le hic est l'accolade fermante. Une fois qu'elle s'exécute, cette mémoire a disparu.

Le pointeur pendouillant

Voici le bug que tout programmeur C écrit une fois :

/* CASSE : renvoie l'adresse d'une memoire qui n'existe plus */
int *make_counter(void) {
    int count = 0;
    return &count;          /* count meurt a cette accolade */
}

int main(void) {
    int *p = make_counter();
    *p = 5;                 /* ecriture dans une trame de pile morte */
    return 0;
}

&count était une adresse parfaitement valide pendant l'exécution de make_counter. Au retour, cet espace de pile est remis à la fonction appelée ensuite, donc p pointe désormais dans les variables locales de quelqu'un d'autre. Lire donne du garbage ; écrire les corrompt. GCC et Clang avertissent sur cette forme exacte (-Wreturn-local-addr), alors compilez avec les avertissements activés.

Le même bug se déguise avec les tableaux, et là l'avertissement ne se déclenche souvent pas :

#include <stdio.h>
#include <string.h>

/* Correct : l'appelant fournit le stockage, qui survit donc a l'appel. */
void make_greeting(char *out, size_t size, const char *name) {
    snprintf(out, size, "Bonjour, %s !", name);
}

int main(void) {
    char message[64];
    make_greeting(message, sizeof message, "Ada");
    printf("%s\n", message);
    return 0;
}

La version cassée de cette fonction construirait le texte dans un char buf[64] local et ferait return buf; - renvoyant l'adresse d'un tampon qui cesse d'exister au même instant.

Trois façons de corriger

1. L'appelant fournit le tampon (montré ci-dessus). Aucune allocation, aucune question de propriété, et le style le plus courant dans les bibliothèques C. La fonction prend la taille pour pouvoir y rester.

2. Renvoyer de la mémoire du tas, et dire qui la libère.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* Renvoie une chaine fraichement allouee ; l'appelant doit la liberer. */
char *make_greeting(const char *name) {
    size_t size = strlen(name) + 16;
    char *out = malloc(size);
    if (out == NULL) {
        return NULL;
    }
    snprintf(out, size, "Bonjour, %s !", name);
    return out;
}

int main(void) {
    char *message = make_greeting("Ada");
    if (message == NULL) {
        return 1;
    }
    printf("%s\n", message);
    free(message);
    return 0;
}

Le bloc du tas survit à la fonction par conception - c'est tout l'intérêt de la mémoire dynamique. Le coût est le commentaire de propriété et le free de l'appelant.

3. Utiliser le stockage statique, quand un tampon partagé unique est acceptable :

#include <stdio.h>

int *next_id(void) {
    static int id = 0;      /* une seule instance, vit pour tout le programme */
    id++;
    return &id;             /* sur : le stockage statique ne disparait jamais */
}

int main(void) {
    printf("%d\n", *next_id());
    printf("%d\n", *next_id());
    printf("%d\n", *next_id());
    return 0;
}

static dans une fonction garde la portée de la variable locale tout en lui donnant la durée de vie du programme, donc renvoyer son adresse est légal. Le compromis est qu'il n'y en a jamais qu'une : chaque appelant la partage, ce qui rend ce motif inutilisable en code multifil et surprenant même en monofil quand deux appelants détiennent le pointeur en même temps.

La taille : là où la pile s'épuise

L'espace de pile est petit et fixe. Le fil principal obtient typiquement 1 Mo sous Windows et 8 Mo sous Linux ; un fil créé en obtient souvent bien moins. Le tas est borné par la mémoire disponible du système.

void bad(void) {
    int huge[1000000];      /* ~4 Mo de pile - plante probablement a l'entree */
    huge[0] = 1;
}

Il n'y a aucun diagnostic et aucun NULL à vérifier : le programme meurt simplement, généralement avec une erreur de segmentation, avant l'exécution de la première ligne du corps. La version sur le tas signale l'échec correctement :

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    size_t n = 1000000;

    int *huge = malloc(n * sizeof *huge);
    if (huge == NULL) {
        fprintf(stderr, "impossible d'allouer %zu int\n", n);
        return 1;
    }

    huge[0] = 1;
    huge[n - 1] = 2;
    printf("%d ... %d (%zu octets)\n", huge[0], huge[n - 1], n * sizeof *huge);

    free(huge);
    return 0;
}

Une récursion profonde épuise la pile de la même façon, une trame à la fois - une fonction récursive emballée est la cause la plus courante de débordement de pile en pratique.

Coût et localité

L'allocation sur la pile est une opération arithmétique sur un registre. L'allocation sur le tas est un appel de bibliothèque qui cherche un bloc approprié, peut prendre un verrou, et demande parfois plus de mémoire au système d'exploitation. Dans une boucle sollicitée, cette différence est mesurable.

Les données de pile sont aussi compactes et récemment touchées, donc elles ont tendance à être en cache. Les blocs du tas peuvent être éparpillés. Aucun de ces faits ne devrait à lui seul dicter une conception - la justesse de la durée de vie passe d'abord - mais entre deux conceptions toutes deux correctes, celle sur la pile est généralement la plus rapide.

Voir les régions

Afficher des adresses rend la disposition concrète. Les valeurs exactes diffèrent à chaque exécution (les systèmes modernes les randomisent), mais le regroupement est visible :

#include <stdio.h>
#include <stdlib.h>

int global_value = 1;

int main(void) {
    static int static_value = 2;
    int local_value = 3;

    int *heap_value = malloc(sizeof *heap_value);
    if (heap_value == NULL) {
        return 1;
    }
    *heap_value = 4;

    printf("globale  : %p\n", (void *)&global_value);
    printf("statique : %p\n", (void *)&static_value);
    printf("tas      : %p\n", (void *)heap_value);
    printf("locale   : %p\n", (void *)&local_value);

    free(heap_value);
    return 0;
}

La globale et la statique sont voisines ; le bloc du tas est ailleurs ; la locale est typiquement loin des deux. Convertissez en void * pour %p - c'est ce que le spécificateur de format exige.

Choisir

Utilisez la pile quand :

• la taille est connue à la compilation,
• les données ne sont nécessaires que dans cette fonction et celles qu'elle appelle,
• et que c'est petit - quelques kilooctets, pas des mégaoctets.

Utilisez le tas quand :

• la taille dépend d'une entrée, d'un fichier ou d'un calcul,
• les données doivent survivre à la fonction qui les a créées,
• ou que c'est assez grand pour menacer la limite de la pile.

Utilisez le statique quand :

• exactement une instance doit exister pour tout le programme,
• et que la partager entre tous les appelants est réellement correct.

Le choix par défaut est la pile. Prenez le tas quand l'une de ses trois raisons s'applique, et quand vous le faites, suivez les règles de propriété de fuites de mémoire pour que le bloc dont vous avez gagné la durée de vie soit quand même rendu.

Deux bugs en miroir

Ils méritent d'être nommés ensemble, car ce sont les deux réponses à la même question de durée de vie :

• Le pointeur pendouillant - la mémoire est morte avant le pointeur. Renvoyer &local, ou utiliser un pointeur après free. Le programme lit ou écrit un stockage qui appartient maintenant à autre chose.
• La fuite de mémoire - le pointeur est mort avant la mémoire. Perdre la dernière référence vers un bloc malloc. Rien ne casse immédiatement ; le processus ne fait que grossir.

Les deux viennent d'un décalage entre la durée pendant laquelle les données doivent vivre et la région où vous les avez mises. Décidez la durée de vie d'abord, et la région suit.