Débogage avancé/Travail pratique/Débordement de pile

Début de la boite de navigation du travail pratique

But de ce TP

Depuis la création et l'implantation du langage Algol dans les années 1958-1960, la plupart des langages de programmations permettent d'exécuter des fonction récursives. L'idée de base est d'avoir une zone de mémoire dédiée à enregistrer les informations pour cela: la pile.

Un petit peu de cette pile est consommé par chaque appel récursif pour y stocker les variables locales, les arguments de la fonction, l'adresse de retour, tous liés à l'appel. Cet espace n'est rendu qu'à la terminaison de la fonction. Il n'est donc pas possible d'empiler à l'infini des appels récursifs en C. Certains langages fonctionnels comme OCaml, LISP (et ses descendants: Scheme, Clojure, etc.) ou Haskell, sont capables d'enlever une récursion terminale pour rendre le programme itératif et ainsi, éliminer le problème. Le langage Go, augmente la pile jusqu'à plusieurs Gio ce qui repousse le problème, mais ne l'élimine pas.

Le code à déboguer

Créer un fichier bug_stackoverflow.c contenant le code suivant.

#include <stdio.h>

typedef struct elem {
  struct elem *next;
} Elem;

// parcours récursif de la liste donné en argument
// Bug: débordement de la pile dès que la liste est longue
int list_length_functional_style(Elem *h) {
  if (h == NULL)
    return 0;

  return 1 + list_length_functional_style(h->next);
}

int main() {
  // Création d'une petite liste circulaire, dans la pile aussi
  Elem a;
  Elem b = {.next = &a};
  a = (Elem){.next = &b};
  Elem *head = &a;

  printf("list length: %d\n", list_length_functional_style(head));
  return 0;
}

Les consignes

Détecter le bug

Le programme bug_stackoverflow.c utilise une liste circulaire pour appeler à l'infini une fonction récursive. Une fonction récursive utilise une pile pour ses variables locales et ses paramètres. La pile est juste un bloc de mémoire contigüe de quelques Mio par défaut. La commande ulimit -a vous donne la liste de vos limites.

1. Compiler et lancer le programme. C'est la gestion de la pagination et de la mémoire virtuelle du processeur (une détection matérielle) et du système d'exploitation (traitement logiciel de l'erreur détectée) qui désigne l'utilisation illégale de mémoire au-delà de la pile (SEGFAULT). Mais un SEGFAULT ressemble à tous les autres accès illégaux que vous pouvez faire avec un pointeur.
2. Lancez le programme avec Valgrind. Il détecte également le problème. Mais surtout, Valgrind vous indique que c'est un débordement de pile et pas autre chose !

Tracer l'état du programme sans le changer en permanence

Pour déboguer un code (ici, comprendre que la liste est circulaire), une première méthode est d'ajouter des printf pour obtenir des traces. Cela demande de savoir à l'avance ce que l'on veut observer, puis d'éditer le code, puis de recompiler, puis de réexécuter, puis de recommencer le tout si la trace ne suffit pas. C'est long !

Votre débogueur est parfaitement capable d'ajouter dynamiquement ces traces sans avoir à changer le code et recompiler le programme.

1. Lancer gdb avec le programme en argument dans un terminal. Démarrer le programme. Afficher le code de la fonction fautive. Demander l'affichage de h et de h->next à chaque passage à la ligne avant le return. Redémarrez le programme en confirmant le redémarrage depuis le début. Voilà, vous avez votre trace ! Générez la trace en soi est long car gdb fait un arrêt à chaque passage à la ligne indiquée et votre terminal n'est pas aussi rapide que vous le pensez, mais vous n'hésitez pas à faire Control-C pour interrompre l'exécution.

Solution

Vous devriez avoir tapé les commandes suivantes (certains affichages de Valgrind sont omis):

Pour la détection du bug:

$ /bug_stackoverflow 
Erreur de segmentation (core dumped)
$ valgrind ./bug_stackoverflow
[...]
==8672== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
== 8672 ==
==8672== Process terminating with default action of signal 11 (SIGSEGV)
==8672==  Access not within mapped region at address 0x1FFE801FF8
==8672== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==8672==    at 0x109141: functional_list_length (bug_stackoverflow.c:22)
[...]

Pour la génération de la trace:

you@ensipc$ gdb ./bug_stackoverflow
[...]
(gdb) break list_length_functional_style
(gdb) run
(gdb) list # assume return is line 13
(gdb) dprintf 12,"h: %x, h->next: %x\n", h, h->next
(gdb) run # then confirm the restart from beginning
          # then Control-C to stop the execution
(gdb) where # then quit, otherwise, view many many frames