Pile d'appels - Call stack

En informatique , une pile d'appels est une structure de données de pile qui stocke des informations sur les sous - programmes actifs d'un programme informatique . Ce type de pile est également connu comme une pile d'exécution , la pile de programme , pile de contrôle , pile d' exécution , ou la pile de la machine , et est souvent raccourci juste « la pile ». Bien que la maintenance de la pile d'appels soit importante pour le bon fonctionnement de la plupart des logiciels , les détails sont normalement cachés et automatiques dans les langages de programmation de haut niveau . De nombreux jeux d' instructions informatiques fournissent des instructions spéciales pour la manipulation des piles.

Une pile d'appels est utilisée à plusieurs fins connexes, mais la principale raison d'en avoir une est de garder une trace du point auquel chaque sous-programme actif doit rendre le contrôle à la fin de son exécution. Un sous-programme actif est un sous-programme qui a été appelé, mais dont l'exécution n'est pas encore terminée, après quoi le contrôle doit être rendu au point d'appel. De telles activations de sous-programmes peuvent être imbriquées à n'importe quel niveau (récursif comme cas particulier), d'où la structure de la pile. Par exemple, si un sous DrawSquare- programme appelle un sous-programme à DrawLinepartir de quatre endroits différents, DrawLinedoit savoir où retourner lorsque son exécution est terminée. Pour ce faire, l' adresse qui suit l' instruction qui saute à DrawLine, l' adresse de retour , est placée en haut de la pile d'appels à chaque appel.

La description

Étant donné que la pile d'appels est organisée comme une pile , l'appelant pousse l'adresse de retour sur la pile et le sous-programme appelé, lorsqu'il se termine, extrait ou supprime l'adresse de retour de la pile d'appels et transfère le contrôle à cette adresse. Si un sous-programme appelé appelle encore un autre sous-programme, il poussera une autre adresse de retour sur la pile d'appels, et ainsi de suite, les informations s'empilant et se désempilant comme le programme l'exige. Si le push consomme tout l'espace alloué à la pile d'appels, une erreur appelée débordement de pile se produit, provoquant généralement le plantage du programme . L'ajout d'une entrée de sous-programme à la pile d'appels est parfois appelé « enroulement » ; à l'inverse, supprimer des entrées est un "déroulement".

Il y a généralement exactement une pile d'appels associée à un programme en cours d'exécution (ou plus précisément, à chaque tâche ou thread d'un processus ), bien que des piles supplémentaires puissent être créées pour la gestion des signaux ou le multitâche coopératif (comme avec setcontext ). Puisqu'il n'y en a qu'un dans ce contexte important, il peut être appelé la pile (implicitement, "de la tâche"); Cependant, dans le langage de programmation Forth la pile de données ou pile paramètre est plus explicitement accessible que la pile d'appel et est communément appelé la pile (voir ci - dessous).

Dans les langages de programmation de haut niveau , les spécificités de la pile d'appels sont généralement cachées au programmeur. Ils n'ont accès qu'à un ensemble de fonctions, et non à la mémoire de la pile elle-même. Ceci est un exemple d' abstraction . La plupart des langages d'assemblage , d'autre part, nécessitent que les programmeurs soient impliqués dans la manipulation de la pile. Les détails réels de la pile dans un langage de programmation dépendent du compilateur , du système d'exploitation et du jeu d'instructions disponible .

Fonctions de la pile d'appels

Comme indiqué ci-dessus, l'objectif principal d'une pile d'appels est de stocker les adresses de retour . Lorsqu'un sous-programme est appelé, l'emplacement (adresse) de l'instruction à laquelle le sous-programme d'appel peut reprendre ultérieurement doit être enregistré quelque part. L'utilisation d'une pile pour enregistrer l'adresse de retour présente des avantages importants par rapport aux conventions d'appel alternatives . La première est que chaque tâche peut avoir sa propre pile, et donc la sous-routine peut être thread-safe , c'est-à-dire qu'elle peut être active simultanément pour différentes tâches faisant différentes choses. Un autre avantage est qu'en fournissant la réentrance , la récursivité est automatiquement prise en charge. Lorsqu'une fonction s'appelle récursivement, une adresse de retour doit être stockée pour chaque activation de la fonction afin qu'elle puisse être utilisée ultérieurement pour revenir de l'activation de la fonction. Les structures de pile fournissent cette capacité automatiquement.

Selon la langue, le système d'exploitation et l'environnement de la machine, une pile d'appels peut servir à des fins supplémentaires, notamment :

Stockage local des données
Voir aussi : allocation de mémoire basée sur la pile
Un sous-programme a souvent besoin d'espace mémoire pour stocker les valeurs des variables locales , les variables qui ne sont connues que dans le sous-programme actif et ne conservent pas les valeurs après son retour. Il est souvent pratique d'allouer de l'espace à cette utilisation en déplaçant simplement le haut de la pile suffisamment pour fournir l'espace. C'est très rapide par rapport à l'allocation dynamique de mémoire , qui utilise l' espace du tas . Notez que chaque activation séparée d'un sous-programme obtient son propre espace séparé dans la pile pour les locaux.
Passage de paramètres
Les sous-programmes nécessitent souvent que les valeurs des paramètres leur soient fournies par le code qui les appelle, et il n'est pas rare que de l'espace pour ces paramètres puisse être disposé dans la pile d'appels. Généralement, s'il n'y a que quelques petits paramètres, les registres du processeur seront utilisés pour transmettre les valeurs, mais s'il y a plus de paramètres que ce qui peut être géré de cette manière, de l'espace mémoire sera nécessaire. La pile d'appels fonctionne bien comme emplacement pour ces paramètres, d'autant plus que chaque appel à un sous-programme, qui aura des valeurs différentes pour les paramètres, se verra attribuer un espace séparé sur la pile d'appels pour ces valeurs.
Pile d'évaluation
Les opérandes pour les opérations arithmétiques ou logiques sont le plus souvent placés dans des registres et exploités là-bas. Cependant, dans certaines situations, les opérandes peuvent être empilés jusqu'à une profondeur arbitraire, ce qui signifie que quelque chose de plus que des registres doit être utilisé (c'est le cas du débordement de registre ). La pile de ces opérandes, un peu comme celle d'un calculateur RPN , est appelée pile d'évaluation et peut occuper de l'espace dans la pile d'appels.
Pointeur vers l'instance actuelle
Certains langages orientés objet (par exemple, C++ ), stockent le pointeur this avec les arguments de fonction dans la pile d'appels lors de l'appel de méthodes. Le pointeur this pointe vers l' instance d' objet associée à la méthode à appeler.
Contexte de sous-programme englobant
Certains langages de programmation (par exemple, Pascal et Ada ) prennent en charge la déclaration de sous - routines imbriquées , qui sont autorisées à accéder au contexte de leurs routines englobantes, c'est-à-dire les paramètres et les variables locales dans la portée des routines externes. Une telle imbrication statique peut se répéter - une fonction déclarée dans une fonction déclarée dans une fonction... L'implémentation doit fournir un moyen par lequel une fonction appelée à n'importe quel niveau d'imbrication statique peut référencer le cadre englobant à chaque niveau d'imbrication englobant. Généralement, cette référence est implémentée par un pointeur vers le cadre de l'instance la plus récemment activée de la fonction englobante, appelé « lien descendant » ou « lien statique », pour le distinguer du « lien dynamique » qui fait référence à l'appelant immédiat ( qui n'a pas besoin d'être la fonction parent statique).

Au lieu d'un lien statique, les références aux trames statiques englobantes peuvent être collectées dans un tableau de pointeurs connu sous le nom d' affichage qui est indexé pour localiser une trame souhaitée. La profondeur de l'imbrication lexicale d'une routine est une constante connue, donc la taille de l'affichage d'une routine est fixe. De plus, le nombre de portées contenantes à parcourir est connu, l'index dans l'affichage est également fixe. Habituellement, l'affichage d'une routine est situé dans son propre cadre de pile, mais le Burroughs B6500 a implémenté un tel affichage dans le matériel qui prend en charge jusqu'à 32 niveaux d'imbrication statique.
Les entrées d'affichage indiquant des portées contenant sont obtenues à partir du préfixe approprié de l'affichage de l'appelant. Une routine interne qui se répète crée des trames d'appel distinctes pour chaque invocation. Dans ce cas, tous les liens statiques de la routine interne pointent vers le même contexte de routine externe.
Autre état de retour
En plus de l'adresse de retour, dans certains environnements, il peut y avoir d'autres états de la machine ou du logiciel qui doivent être restaurés lorsqu'un sous-programme revient. Cela peut inclure des éléments tels que le niveau de privilège, les informations de gestion des exceptions, les modes arithmétiques, etc. Si nécessaire, cela peut être stocké dans la pile d'appels tout comme l'adresse de retour.

La pile d'appels typique est utilisée pour l'adresse de retour, les locaux et les paramètres (appelée trame d'appel ). Dans certains environnements, il peut y avoir plus ou moins de fonctions affectées à la pile d'appels. Dans le langage de programmation Forth , par exemple, normalement, seules l'adresse de retour, les paramètres et index de boucle comptés, et éventuellement les variables locales sont stockés sur la pile d'appels (qui dans cet environnement est appelée la pile de retour ), bien que toutes les données puissent être temporairement placées là en utilisant un code spécial de gestion de la pile de retour tant que les besoins des appels et des retours sont respectés ; les paramètres sont habituellement stockés sur un séparé pile de données ou pile paramètre , généralement appelé la pile dans la terminologie Forth , même si il y a une pile d'appel , car il est généralement accessible de manière plus explicite. Certains Forth ont également une troisième pile pour les paramètres à virgule flottante .

Structure

Disposition de la pile d'appels pour les piles à croissance ascendante

Une pile d'appels est composée de trames de pile (également appelées enregistrements d' activation ou trames d'activation ). Ce sont des structures de données dépendantes de la machine et dépendantes de l' ABI contenant des informations d'état de sous-programme. Chaque trame de pile correspond à un appel à un sous-programme qui ne s'est pas encore terminé par un retour. Par exemple, si un sous-programme nommé DrawLineest en cours d'exécution, ayant été appelé par un sous-programme DrawSquare, la partie supérieure de la pile d'appels peut être disposée comme dans l'image adjacente.

Un diagramme comme celui-ci peut être dessiné dans les deux sens tant que le placement du dessus, et donc la direction de croissance de la pile, est compris. De plus, indépendamment de cela, les architectures diffèrent selon que les piles d'appels croissent vers des adresses supérieures ou vers des adresses inférieures. La logique du schéma est indépendante du choix d'adressage.

Le cadre de pile en haut de la pile est pour la routine en cours d'exécution. Le cadre de pile comprend généralement au moins les éléments suivants (dans l'ordre push) :

  • les arguments (valeurs des paramètres) passés à la routine (le cas échéant) ;
  • l'adresse de retour à l'appelant de la routine (par exemple dans le DrawLinecadre de pile, une adresse dans DrawSquarele code de '); et
  • espace pour les variables locales de la routine (le cas échéant).

Empiler et cadrer les pointeurs

Lorsque les tailles des cadres de pile peuvent différer, par exemple entre différentes fonctions ou entre les appels d'une fonction particulière, le fait de retirer un cadre de la pile ne constitue pas un décrément fixe du pointeur de pile . Au retour de la fonction, le pointeur de pile est à la place restauré au pointeur de trame , la valeur du pointeur de pile juste avant que la fonction ne soit appelée. Chaque cadre de pile contient un pointeur de pile vers le haut du cadre immédiatement en dessous. Le pointeur de pile est un registre mutable partagé entre toutes les invocations. Un pointeur de trame d'une invocation donnée d'une fonction est une copie du pointeur de pile tel qu'il était avant que la fonction ne soit invoquée.

Les emplacements de tous les autres champs du cadre peuvent être définis par rapport au haut du cadre, en tant que décalages négatifs du pointeur de pile, ou par rapport au haut du cadre en dessous, en tant que décalages positifs du pointeur de cadre. L'emplacement du pointeur de trame lui-même doit être défini de manière inhérente comme un décalage négatif du pointeur de pile.

Mémorisation de l'adresse dans le cadre de l'appelant

Dans la plupart des systèmes, une trame de pile a un champ pour contenir la valeur précédente du registre de pointeur de trame, la valeur qu'elle avait pendant l'exécution de l'appelant. Par exemple, la trame de pile de DrawLineaurait un emplacement mémoire contenant la valeur du pointeur de trame qui DrawSquareutilise (non illustré dans le diagramme ci-dessus). La valeur est enregistrée lors de l'entrée dans le sous-programme et restaurée au retour. Le fait d'avoir un tel champ à un emplacement connu dans le cadre de la pile permet au code d'accéder successivement à chaque cadre sous le cadre de la routine en cours d'exécution, et permet également à la routine de restaurer facilement le pointeur de cadre sur le cadre de l' appelant , juste avant son retour.

Routines imbriquées lexicalement

Informations complémentaires : fonction imbriquée et variable non locale

Les langages de programmation qui prennent en charge les sous-routines imbriquées ont également un champ dans la trame d'appel qui pointe vers la trame de pile de la dernière activation de la procédure qui encapsule le plus étroitement l'appelé, c'est-à-dire la portée immédiate de l'appelé. C'est ce qu'on appelle un lien d'accès ou un lien statique (car il garde une trace de l'imbrication statique pendant les appels dynamiques et récursifs) et fournit à la routine (ainsi qu'à toute autre routine qu'elle peut invoquer) l'accès aux données locales de ses routines d'encapsulation à chaque imbrication niveau. Certaines architectures, compilateurs ou cas d'optimisation stockent un lien pour chaque niveau englobant (pas seulement celui englobant immédiatement), de sorte que les routines profondément imbriquées qui accèdent à des données superficielles n'aient pas à traverser plusieurs liens ; cette stratégie est souvent appelée « affichage ».

Les liens d'accès peuvent être optimisés lorsqu'une fonction interne n'accède à aucune donnée locale (non constante) dans l'encapsulation, comme c'est le cas avec les fonctions pures communiquant uniquement via des arguments et des valeurs de retour, par exemple. Certains ordinateurs historiques, tels que les grands systèmes de Burroughs , avaient des "registres d'affichage" spéciaux pour prendre en charge les fonctions imbriquées, tandis que les compilateurs pour la plupart des machines modernes (comme l'omniprésent x86) réservent simplement quelques mots sur la pile pour les pointeurs, selon les besoins.

Chevaucher

À certaines fins, le cadre de pile d'un sous-programme et celui de son appelant peuvent être considérés comme se chevauchant, le chevauchement consistant en la zone où les paramètres sont passés de l'appelant à l'appelé. Dans certains environnements, l'appelant pousse chaque argument sur la pile, étendant ainsi son cadre de pile, puis invoque l'appelé. Dans d'autres environnements, l'appelant a une zone pré-allouée en haut de son cadre de pile pour contenir les arguments qu'il fournit aux autres sous-routines qu'il appelle. Cette zone est parfois appelée zone d'arguments sortants ou zone de légende . Selon cette approche, la taille de la zone est calculée par le compilateur pour être la plus grande nécessaire à tout sous-programme appelé.

Utiliser

Traitement du site d'appel

Habituellement, la manipulation de la pile d'appels nécessaire sur le site d'un appel à un sous-programme est minimale (ce qui est bien car il peut y avoir de nombreux sites d'appel pour chaque sous-programme à appeler). Les valeurs des arguments réels sont évaluées sur le site d'appel, car elles sont spécifiques à l'appel particulier, et sont soit poussées sur la pile, soit placées dans des registres, comme déterminé par la convention d'appel utilisée . L'instruction d'appel réelle, telle que "branche et lien", est alors typiquement exécutée pour transférer le contrôle au code du sous-programme cible.

Traitement des entrées de sous-programme

Dans le sous-programme appelé, le premier code exécuté est généralement appelé le prologue du sous - programme , car il fait le ménage nécessaire avant que le code pour les instructions du sous-programme ne commence.

Pour les architectures de jeu d'instructions dans lesquelles l'instruction utilisée pour appeler un sous-programme met l'adresse de retour dans un registre, plutôt que de la pousser sur la pile, le prologue enregistre généralement l'adresse de retour en poussant la valeur sur la pile d'appel, bien que si l'appelé le sous-programme n'appelle aucune autre routine, il peut laisser la valeur dans le registre. De même, les valeurs actuelles du pointeur de pile et/ou du pointeur de trame peuvent être poussées.

Si des pointeurs de trame sont utilisés, le prologue définira généralement la nouvelle valeur du registre de pointeur de trame à partir du pointeur de pile. L'espace sur la pile pour les variables locales peut ensuite être alloué en modifiant progressivement le pointeur de pile.

Le langage de programmation Forth permet un enroulement explicite de la pile d'appels (appelée ici "pile de retour").

Traitement des retours

Lorsqu'un sous-programme est prêt à revenir, il exécute un épilogue qui annule les étapes du prologue. Cela restaurera généralement les valeurs de registre enregistrées (telles que la valeur du pointeur de trame) à partir du cadre de la pile, retirera l'intégralité du cadre de la pile de la pile en modifiant la valeur du pointeur de la pile, et enfin passera à l'instruction à l'adresse de retour. Dans de nombreuses conventions d'appel, les éléments sortis de la pile par l'épilogue incluent les valeurs d'argument d'origine, auquel cas il n'y a généralement pas d'autres manipulations de pile qui doivent être effectuées par l'appelant. Avec certaines conventions d'appel, cependant, il est de la responsabilité de l'appelant de supprimer les arguments de la pile après le retour.

Déroulement

Le retour de la fonction appelée fera sortir le cadre supérieur de la pile, laissant peut-être une valeur de retour. L'action plus générale consistant à retirer une ou plusieurs images de la pile pour reprendre l'exécution ailleurs dans le programme est appelée déroulement de la pile et doit être effectuée lorsque des structures de contrôle non locales sont utilisées, telles que celles utilisées pour la gestion des exceptions . Dans ce cas, le cadre de pile d'une fonction contient une ou plusieurs entrées spécifiant des gestionnaires d'exceptions. Lorsqu'une exception est levée, la pile est déroulée jusqu'à ce qu'un gestionnaire soit trouvé qui soit prêt à gérer (attraper) le type de l'exception levée.

Certaines langues ont d'autres structures de contrôle qui nécessitent un déroulement général. Pascal permet à une instruction goto globale de transférer le contrôle d'une fonction imbriquée vers une fonction externe précédemment invoquée. Cette opération nécessite le déroulement de la pile, en supprimant autant de cadres de pile que nécessaire pour restaurer le contexte approprié pour transférer le contrôle à l'instruction cible dans la fonction externe englobante. De même, C a les fonctions setjmpetlongjmp qui agissent comme des gotos non locaux. Common Lisp permet de contrôler ce qui se passe lorsque la pile est déroulée en utilisant l' unwind-protectopérateur spécial.

Lors de l'application d'une continuation , la pile est (logiquement) déroulée puis rembobinée avec la pile de la continuation. Ce n'est pas la seule façon d'implémenter des continuations ; par exemple, en utilisant plusieurs piles explicites, l'application d'une continuation peut simplement activer sa pile et enrouler une valeur à transmettre. Le langage de programmation Scheme permet à des thunks arbitraires d'être exécutés à des points spécifiés lors du "déroulement" ou du "rembobinage" de la pile de contrôle lorsqu'une continuation est invoquée.

Inspection

Voir aussi : Profilage (programmation informatique)

La pile d'appels peut parfois être inspectée pendant l'exécution du programme. Selon la façon dont le programme est écrit et compilé, les informations sur la pile peuvent être utilisées pour déterminer des valeurs intermédiaires et des traces d'appel de fonction. Cela a été utilisé pour générer des tests automatisés à grain fin et, dans des cas comme Ruby et Smalltalk, pour implémenter des continuations de première classe. À titre d'exemple, le débogueur GNU (GDB) implémente une inspection interactive de la pile d'appels d'un programme C en cours d'exécution, mais en pause.

Prendre des échantillons réguliers de la pile d'appels peut être utile pour profiler les performances des programmes, car si le pointeur d'un sous-programme apparaît plusieurs fois sur les données d'échantillonnage de la pile d'appels, il s'agit probablement d'un goulot d'étranglement du code et doit être inspecté pour des problèmes de performances.

Sécurité

Article principal: débordement de tampon de pile

Dans un langage avec des pointeurs libres ou des écritures de tableau non vérifiées (comme en C), le mélange de données de flux de contrôle qui affectent l'exécution de code (les adresses de retour ou les pointeurs de trame enregistrés) et de données de programme simples (paramètres ou valeurs de retour ) dans une pile d'appels est un risque de sécurité, éventuellement exploitable via des débordements de tampon de pile en tant que type de débordement de tampon le plus courant .

L'une de ces attaques consiste à remplir un tampon avec du code exécutable arbitraire, puis à déborder le même ou un autre tampon pour écraser une adresse de retour avec une valeur qui pointe directement vers le code exécutable. En conséquence, lorsque la fonction revient, l'ordinateur exécute ce code. Ce type d'attaque peut être facilement bloqué avec W^X . Des attaques similaires peuvent réussir même avec la protection W^X activée, y compris l' attaque return-to-libc ou les attaques provenant de la programmation orientée retour . Diverses mesures d'atténuation ont été proposées, telles que le stockage des tableaux dans un emplacement complètement séparé de la pile de retour, comme c'est le cas dans le langage de programmation Forth.

Voir également

Les références

Lectures complémentaires

Liens externes