Dépassement de pile - Définition

Introduction

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 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.

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 :

• 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.

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.

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.