Débordement de pile - Stack overflow
Dans le logiciel, un débordement de pile se produit si le pointeur de pile d'appels dépasse la limite de pile . La pile d'appels peut consister en une quantité limitée d' espace d'adressage , souvent déterminée au début du programme. La taille de la pile d'appels dépend de nombreux facteurs, notamment le langage de programmation, l'architecture de la machine, le multi-threading et la quantité de mémoire disponible. Lorsqu'un programme tente d'utiliser plus d'espace que ce qui est disponible sur la pile d'appels (c'est-à-dire lorsqu'il tente d'accéder à la mémoire au-delà des limites de la pile d'appels, ce qui est essentiellement un débordement de tampon ), on dit que la pile déborde , ce qui entraîne généralement un plantage du programme.
Causes
Récursion infinie
La cause la plus courante de débordement de pile est une récursivité excessivement profonde ou infinie, dans laquelle une fonction s'appelle elle-même tellement de fois que l'espace nécessaire pour stocker les variables et les informations associées à chaque appel est plus que ce que peut contenir la pile.
Un exemple de récursivité infinie en C .
int foo()
{
return foo();
}
La fonction foo , lorsqu'elle est invoquée, continue de s'appeler, allouant à chaque fois de l'espace supplémentaire sur la pile, jusqu'à ce que la pile déborde, entraînant une erreur de segmentation . Cependant, certains compilateurs implémentent l' optimisation d'appel de queue , permettant à une récursivité infinie d'une sorte spécifique — la récursivité de queue — de se produire sans débordement de pile. Cela fonctionne car les appels de récursivité terminale n'occupent pas d'espace de pile supplémentaire.
Certaines options du compilateur C permettront effectivement l' optimisation des appels de queue ; par exemple, la compilation du programme simple ci-dessus à l'aide de gcc avec -O1entraînera une erreur de segmentation, mais pas lors de l'utilisation de -O2ou -O3, car ces niveaux d'optimisation impliquent l' -foptimize-sibling-callsoption du compilateur. D'autres langages, tels que Scheme , exigent que toutes les implémentations incluent la récursivité terminale dans le cadre de la norme de langage.
Récursion très profonde
Une fonction récursive qui se termine en théorie mais provoque un débordement de tampon de pile d'appels en pratique peut être corrigée en transformant la récursivité en boucle et en stockant les arguments de la fonction dans une pile explicite (plutôt que l'utilisation implicite de la pile d'appels). Ceci est toujours possible, car la classe des fonctions récursives primitives est équivalente à la classe des fonctions calculables LOOP. Considérez cet exemple en pseudo-code de type C++ :
void function (argument)
{
if (condition)
function (argument.next);
}
|
stack.push(argument);
while (!stack.empty())
{
argument = stack.pop();
if (condition)
stack.push(argument.next);
}
|
Une fonction récursive primitive comme celle de gauche peut toujours être transformée en boucle comme celle de droite.
Une fonction comme l'exemple ci-dessus à gauche ne serait pas un problème dans un environnement prenant en charge l' optimisation des appels de queue ; cependant il est toujours possible de créer une fonction récursive qui peut entraîner un débordement de pile dans ces langages. Considérez l'exemple ci-dessous de deux fonctions d'exponentiation entières simples.
int pow(int base, int exp) {
if (exp > 0)
return base * pow(base, exp - 1);
else
return 1;
}
|
int pow(int base, int exp) {
return pow_accum(base, exp, 1);
}
int pow_accum(int base, int exp, int accum) {
if (exp > 0)
return pow_accum(base, exp - 1, accum * base);
else
return accum;
}
|
Les deux pow(base, exp)fonctions ci-dessus calculent un résultat équivalent, cependant, celle de gauche est susceptible de provoquer un débordement de pile car l'optimisation des appels de queue n'est pas possible pour cette fonction. Lors de l'exécution, la pile de ces fonctions ressemblera à ceci :
pow(5, 4)
5 * pow(5, 3)
5 * (5 * pow(5, 2))
5 * (5 * (5 * pow(5, 1)))
5 * (5 * (5 * (5 * pow(5, 0))))
5 * (5 * (5 * (5 * 1)))
625
|
pow(5, 4)
pow_accum(5, 4, 1)
pow_accum(5, 3, 5)
pow_accum(5, 2, 25)
pow_accum(5, 1, 125)
pow_accum(5, 0, 625)
625
|
Notez que la fonction de gauche doit stocker dans sa pile un expnombre d'entiers, qui sera multiplié lorsque la récursivité se termine et que la fonction renvoie 1. En revanche, la fonction de droite ne doit stocker que 3 entiers à la fois et calcule un résultat intermédiaire qui est passé à son invocation suivante. Comme aucune autre information en dehors de l'appel de fonction en cours ne doit être stockée, un optimiseur de récursivité terminale peut « supprimer » les trames de pile précédentes, éliminant ainsi la possibilité d'un débordement de pile.
Variables de pile très volumineuses
L'autre cause majeure d'un débordement de pile résulte d'une tentative d'allouer plus de mémoire sur la pile qu'il n'y en a, par exemple en créant des variables de tableau locales trop volumineuses. Pour cette raison, certains auteurs recommandent que les tableaux de plus de quelques kilo-octets soient alloués dynamiquement au lieu d'être une variable locale.
Un exemple de très grande variable de pile en C :
int foo()
{
double x[1048576];
}
Sur une implémentation C avec des flottants double précision de 8 octets , le tableau déclaré consomme 8 mégaoctets de données ; s'il y a plus de mémoire que ce qui est disponible sur la pile (comme défini par les paramètres de création de thread ou les limites du système d'exploitation), un débordement de pile se produira.
Les débordements de pile sont aggravés par tout ce qui réduit la taille effective de la pile d'un programme donné. Par exemple, le même programme exécuté sans plusieurs threads peut fonctionner correctement, mais dès que le multi-threading est activé, le programme se bloque. C'est parce que la plupart des programmes avec des threads ont moins d'espace de pile par thread qu'un programme sans prise en charge des threads. Parce que les noyaux sont généralement multi-threads, les personnes novices dans le développement de noyaux sont généralement découragées d'utiliser des algorithmes récursifs ou des tampons de pile volumineux.
Voir également
- Débordement de tampon
- Pile d'appels
- Débordement de tas
- Débordement de la mémoire tampon de la pile
- Double faute
