DĂ©passement de pile
En informatique, un dépassement de pile ou débordement de pile (en anglais, stack overflow) est un bug 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 multithread 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 de 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 commence son exécution dans main(), qui appelle la fonction a(). La fonction a() s’appelant elle-même, ceci crée une boucle infinie.
Récursivité infinie avec deux fonctions (en langage C)
void f();
void g();
int main()
{
f();
return 0;
}
void g()
{
f();
}
void f()
{
g();
}
Le programme commence son exécution dans main(), qui appelle la fonction f(). Ensuite, 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 kilooctets 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];
}
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 multithread peut fonctionner correctement, mais dès que le traitement multithread 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 threads ont moins d'espace pile par thread que le même programme sans fil n’en a pour sa pile unique.
Références
- (en) Burley, James Craig, « Using and Porting GNU Fortran », 1er juin 1991.
- (en) Danny, Kalev, « Understanding Stack Overflow », 5 septembre 2000.
- (en) « An Introduction to Scheme and its Implementation », 19 décembre 1997.
- (en) Feldman, Howard, « Modern Memory Management, Part 2 », 23 novembre 2005.