Débordement de pile

En informatique, un dépassement de pile ou débordement de pile (en anglais, stack overflow) est un bogue causé par un processus qui, lors de l'écriture dans une pile, écrit à l'extérieur de l'espace alloué à la pile, écrasant ainsi des informations nécessaires au processus.

L’expression dépassement de pile peut s’appliquer à toutes les piles. Cependant, lorsque l’on parle de dépassement de pile, on fait habituellement référence à la pile d'exécution. Il serait alors plus précis de dire dépassement de la pile d’exécution, mais les informaticiens ont pris l’habitude de dire simplement dépassement de pile lorsque le contexte indique que la pile dont on parle est la pile d’exécution.

Le reste de cet article traite de dépassement de la pile d’exécution.

Dans tous les langages de programmation, la pile d'exécution contient une quantité limitée de mémoire, habituellement déterminée au début du programme. La taille de la pile d'exécution dépend de nombreux facteurs, incluant le langage de programmation, l’architecture du processeur, l’utilisation du traitement multifil (multi-threading) et de la quantité de mémoire vive disponible. Lorsque trop d’informations sont enregistrées dans la pile d’exécution, la pile déborde et écrase des zones de programme à l’extérieur de la pile. On dit alors qu’il y a dépassement de pile ou dépassement de la pile d’exécution. Il en résulte généralement une interruption du programme.^[1]

Causes principales des dépassements de la pile d’exécution

Un dépassement de pile d’exécution est généralement causé par l'une des deux erreurs de programmation suivantes^[2] :

• une récursivité infinie ;
• une allocation de variables trop grandes dans la pile.

Récursivité infinie

La cause la plus fréquente des dépassements de pile est une récursivité trop profonde ou infinie.

Il est à noter qu’une récursivité profonde ou même infinie ne cause pas toujours un dépassement de pile. En effet, certains langages, comme Scheme, permettent une sorte récursivité infinie, la récursion terminale (en anglais, tail recursion) sans dépassement de pile. Pour ce faire, ces langages transforment la récursivité en une itération, éliminant ainsi l’utilisation de la pile d’exécution.^[3]

Exemples de récursivité infinie

Récursivité infinie avec une seule fonction (en langage C++)

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

Dans l’exemple précédent, le programme appelle la fonction a() et la fonction a() s’appelle elle-même, ce qui crée une boucle infinie.

Récursivité infinie avec deux fonctions (en langage C++)

 void f(void);
 void g(void);

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

 void f(void) {
   g();
 }

 void g(void) {
   f();
 }

Les fonctions f() et g() s’appellent l’une l’autre jusqu'à ce que la pile déborde.

Allocation de variables trop grandes dans la pile

L'autre grande cause de dépassement de pile résulte d'une tentative d'allouer plus d’espace dans la pile que ce que la pile peut contenir. Cela est généralement le résultat de la déclaration de variables locales demandant trop de mémoire. Pour cette raison, les tableaux de plus de quelques kilo-octets devraient toujours être alloués dynamiquement plutôt que comme une variable locale.^[4]

Exemple d’allocation de variables trop grandes dans la pile

 int main() {
   double n[10000000]; 
   return 0;
 }

Le tableau déclaré consomme plus de mémoire que ce qui est disponible dans la pile.

Situations aggravantes de dépassement de pile d’exécution

Les dépassements de la pile d’exécution sont aggravés par tout ce qui réduit la taille de la pile. Par exemple, un programme sans traitement multifil (multi-thread) peut fonctionner correctement, mais dès que le traitement multifil est activé, le même programme peut se retrouver en état de dépassement de pile. La raison en est que la plupart des programmes avec des fils ont moins d'espace pile par fil que le même programme sans fil n’en a pour sa pile unique.

Source

Cet article provient partiellement d'une traduction de l'article correspondant dans la version anglaise de Wikipédia.

Références

Voir aussi

Articles connexes

• Dépassement de tas
• Dépassement de tampon
• Dépassement de tampon de pile d'exécution
• Dépassement d'entier

• Portail de la programmation informatique
• Portail de la sécurité informatique