Comment se produit un "dépassement de pile" et comment l'éviter ?

Question

Comment se produit un débordement de pile et quels sont les meilleurs moyens de s'assurer qu'il ne se produise pas, ou les moyens de l'éviter, en particulier sur les serveurs web, mais d'autres exemples seraient également intéressants ?

Answer 1

Pile

Dans ce contexte, une pile est la mémoire tampon (last in, first out) dans laquelle vous placez les données pendant l'exécution de votre programme. Dernier entré, premier sorti (LIFO) signifie que la dernière chose que vous placez est toujours la première chose que vous récupérez. Si vous placez deux éléments sur la pile, "A" puis "B", la première chose que vous retirez de la pile sera "B", et la suivante "A".

Lorsque vous appelez une fonction dans votre code, l'instruction qui suit l'appel de la fonction est stockée sur la pile, ainsi que tout espace de stockage susceptible d'être écrasé par l'appel de la fonction. La fonction que vous appelez peut utiliser plus de pile pour ses propres variables locales. Lorsqu'elle a terminé, elle libère l'espace de la pile des variables locales qu'elle a utilisé, puis retourne à la fonction précédente.

Débordement de pile

Un débordement de pile se produit lorsque vous avez utilisé plus de mémoire pour la pile que ce que votre programme était censé utiliser. Dans les systèmes embarqués, il se peut que vous ne disposiez que de 256 octets pour la pile, et si chaque fonction occupe 32 octets, vous ne pouvez avoir que 8 appels de fonction - la fonction 1 appelle la fonction 2 qui appelle la fonction 3 qui appelle la fonction 4 .... qui appelle la fonction 8 qui appelle la fonction 9, mais la fonction 9 écrase la mémoire à l'extérieur de la pile. Cela peut écraser la mémoire, le code, etc.

De nombreux programmeurs commettent cette erreur en appelant la fonction A qui appelle ensuite la fonction B, qui appelle ensuite la fonction C, qui appelle ensuite la fonction A. Cela peut fonctionner la plupart du temps, mais il suffit d'une seule entrée erronée pour que le cercle se poursuive indéfiniment jusqu'à ce que l'ordinateur se rende compte que la pile est trop grande.

Les fonctions récursives en sont également la cause, mais si vous écrivez de manière récursive (c'est-à-dire que votre fonction s'appelle elle-même), vous devez en être conscient et utiliser des variables statiques/globales pour éviter la récursion infinie.

En général, le système d'exploitation et le langage de programmation que vous utilisez gèrent la pile, et vous n'avez pas à vous en occuper. Vous devez examiner votre graphe d'appels (une structure arborescente qui montre, à partir de votre fonction principale, ce que chaque fonction appelle) pour voir jusqu'où vont vos appels de fonction et pour détecter les cycles et la récursion qui ne sont pas intentionnels. Les cycles et les récursions intentionnels doivent être vérifiés artificiellement pour détecter les erreurs s'ils s'appellent trop souvent les uns les autres.

Au-delà des bonnes pratiques de programmation et des tests statiques et dynamiques, il n'y a pas grand-chose à faire sur ces systèmes de haut niveau.

Systèmes embarqués

Dans le monde de l'embarqué, en particulier dans les codes à haute fiabilité (automobile, aéronautique, espace), on procède à des révisions et à des vérifications approfondies du code, mais on fait aussi ce qui suit :

• Interdire la récursivité et les cycles - appliqué par une politique et des tests
• Maintenir le code et la pile éloignés l'un de l'autre (code dans la flash, pile dans la RAM, et jamais les deux ne se rencontreront).
• Placez des bandes de garde autour de la pile - une zone vide de la mémoire que vous remplissez avec un nombre magique (généralement une instruction d'interruption logicielle, mais il y a de nombreuses options ici), et des centaines ou des milliers de fois par seconde, vous regardez les bandes de garde pour vous assurer qu'elles n'ont pas été écrasées.
• Utiliser la protection de la mémoire (pas d'exécution sur la pile, pas de lecture ou d'écriture en dehors de la pile).
• Les interruptions n'appellent pas de fonctions secondaires - elles placent des drapeaux, copient des données et laissent l'application se charger de leur traitement (sinon, vous pourriez vous retrouver à 8 niveaux de profondeur dans votre arbre d'appel de fonctions, avoir une interruption, puis sortir encore quelques fonctions à l'intérieur de l'interruption, ce qui provoquerait l'éclatement). Vous avez plusieurs arbres d'appels - un pour les processus principaux et un pour chaque interruption. Si vos interruptions peuvent s'interrompre les unes les autres... eh bien, il y a des dragons...

Langages et systèmes de haut niveau

Mais les langages de haut niveau fonctionnent sur des systèmes d'exploitation :

• Réduire le stockage des variables locales (les variables locales sont stockées sur la pile - bien que les compilateurs soient assez intelligents à ce sujet et placent parfois les grandes variables locales sur le tas si votre arbre d'appel est peu profond).
• Éviter ou limiter strictement la récursivité
• Ne divisez pas trop vos programmes en fonctions de plus en plus petites - même sans compter les variables locales, chaque appel de fonction consomme jusqu'à 64 octets sur la pile (processeur 32 bits, économisant la moitié des registres du CPU, des drapeaux, etc.)
• Gardez votre arbre d'appel superficiel (similaire à l'énoncé ci-dessus)

Serveurs web

La possibilité de contrôler ou même de voir la pile dépend du "bac à sable" dont vous disposez. Il y a de fortes chances que vous puissiez traiter les serveurs web comme n'importe quel autre langage de haut niveau et système d'exploitation - vous n'y êtes pas pour grand-chose, mais vérifiez le langage et la pile de serveurs que vous utilisez. Mais vérifiez le langage et la pile de serveurs que vous utilisez. est Il est possible de faire exploser la pile de votre serveur SQL, par exemple.

-Adam

Answer 2

Un stack overflow se produit lorsque Jeff et Joel veulent offrir au monde un meilleur endroit pour obtenir des réponses à des questions techniques. Il est trop tard pour empêcher ce débordement. Cet "autre site" aurait pu l'éviter en n'étant pas scuzzy ;)

Answer 3

Un débordement de pile dans un code réel se produit très rarement. La plupart des situations dans lesquelles il se produit sont des récursions où la terminaison a été oubliée. Il peut toutefois se produire rarement dans des structures fortement imbriquées, par exemple dans des documents XML particulièrement volumineux. La seule aide réelle consiste à remanier le code pour utiliser un objet de pile explicite au lieu de la pile d'appels.

Answer 4

La plupart des gens vous diront qu'un débordement de pile se produit avec une récursion sans chemin de sortie - bien que ce soit en grande partie vrai, si vous travaillez avec des structures de données suffisamment grandes, même un chemin de sortie de récursion approprié ne vous aidera pas.

Quelques options dans ce cas :

• Recherche en profondeur (Breadth-first)
• Récursion de la queue , spécifique à .Net article de blog (désolé, .Net 32 bits)

Answer 5

La récursivité infinie est un moyen courant d'obtenir une erreur de dépassement de pile. Pour l'éviter, il faut toujours s'assurer qu'il existe un chemin de sortie qui permet à volonté être touché :-)

Une autre façon d'obtenir un débordement de pile (en C/C++, au moins) est de déclarer une énorme variable sur la pile.

char hugeArray[100000000];

Cela suffira.