Comment fonctionne exactement le callstack?

J’essaie de mieux comprendre le fonctionnement des opérations de bas niveau des langages de programmation et en particulier comment ils interagissent avec le système d’exploitation / la CPU. J’ai probablement lu chaque réponse dans chaque thread de stack / tas ici sur Stack Overflow, et ils sont tous shinys. Mais il y a encore une chose que je n’ai pas encore complètement comprise.

Considérez cette fonction dans un pseudo-code qui a tendance à être un code Rust 😉

fn foo() { let a = 1; let b = 2; let c = 3; let d = 4; // line X doSomething(a, b); doAnotherThing(c, d); } 

Voici comment je suppose que la stack ressemble à la ligne X:

 Stack a +-------------+ | 1 | b +-------------+ | 2 | c +-------------+ | 3 | d +-------------+ | 4 | +-------------+ 

Maintenant, tout ce que j’ai lu sur le fonctionnement de la stack, c’est qu’elle obéit ssortingctement aux règles du LIFO (dernier entré, premier sorti). Tout comme un type de données de stack en .NET, Java ou tout autre langage de programmation.

Mais si tel est le cas, alors que se passe-t-il après la ligne X? Parce que de toute évidence, la prochaine chose dont nous avons besoin est de travailler avec a et b , mais cela voudrait dire que le système d’exploitation / CPU (?) Doit d’abord sortir d et c pour revenir à a et b . Mais alors il se tirerait dans le pied, car il a besoin de c et d dans la ligne suivante.

Alors, je me demande ce qui se passe exactement dans les coulisses?

Une autre question connexe. Considérons que nous passons une référence à l’une des autres fonctions comme ceci:

 fn foo() { let a = 1; let b = 2; let c = 3; let d = 4; // line X doSomething(&a, &b); doAnotherThing(c, d); } 

D’après ce que je comprends, cela signifierait que les parameters de doSomething essentiellement la même adresse mémoire telle a et b dans foo . Mais là encore, cela signifie qu’il n’ya pas de pop-up jusqu’à ce que nous arrivions à a et b .

Ces deux cas me font penser que je ne sais pas exactement comment fonctionne la stack et comment elle suit ssortingctement les règles du LIFO .

La stack d’appels peut également être appelée stack de trames.
Les éléments qui sont empilés après le principe LIFO ne sont pas les variables locales, mais la totalité des frameworks de stack (“appels”) des fonctions appelées . Les variables locales sont poussées et déplacées avec ces images dans le prolog de fonction et l’ épilogue , respectivement.

Dans le cadre, l’ordre des variables n’est pas spécifié; Les compilateurs “réorganisent” correctement les positions des variables locales dans un cadre pour optimiser leur alignement afin que le processeur puisse les récupérer aussi rapidement que possible. Le fait crucial est que le décalage des variables par rapport à une adresse fixe est constant pendant toute la durée de vie de la trame – il suffit donc de prendre une adresse d’ancrage, par exemple l’adresse de la trame, et de travailler avec des décalages de cette adresse. les variables. Une telle adresse d’ancrage est en fait contenue dans le soi-disant pointeur de base ou de trame qui est stocké dans le registre EBP. Les décalages, par contre, sont clairement connus au moment de la compilation et sont donc codés en dur dans le code machine.

Ce graphique de Wikipedia montre ce que la stack d’appels typique est structurée comme 1 :

Image d'une pile

Ajoutez le décalage d’une variable que nous voulons accéder à l’adresse contenue dans le pointeur de trame et nous obtenons l’adresse de notre variable. Donc, peu de temps après, le code y accède simplement directement via des décalages constants de compilation à partir du pointeur de base; C’est l’arithmétique simple de pointeur.

Exemple

 #include  int main() { char c = std::cin.get(); std::cout << c; } 

gcc.godbolt.org nous donne

 main: pushq %rbp movq %rsp, %rbp subq $16, %rsp movl std::cin, %edi call std::basic_istream >::get() movb %al, -1(%rbp) movsbl -1(%rbp), %eax movl %eax, %esi movl std::cout, %edi call [... the insertion operator for char, long thing... ] movl $0, %eax leave ret 

.. pour main . J'ai divisé le code en trois sous-sections. Le prolog de la fonction comprend les trois premières opérations:

  • Le pointeur de base est poussé sur la stack.
  • Le pointeur de stack est enregistré dans le pointeur de base
  • Le pointeur de stack est soustrait pour laisser de la place aux variables locales.

Ensuite, cin est déplacé dans le registre EDI 2 et get est appelé; La valeur de retour est dans EAX.

Jusqu'ici tout va bien. Maintenant, la chose intéressante se produit:

L'octet de poids faible de EAX, désigné par le registre à 8 bits AL, est pris et stocké dans l'octet juste après le pointeur de base : c'est-à-dire -1(%rbp) , le décalage du pointeur de base est -1 . Cet octet est notre variable c . Le décalage est négatif car la stack descend vers x86. L'opération suivante stocke c dans EAX: EAX est déplacé vers ESI, cout est déplacé vers EDI, puis l'opérateur d'insertion est appelé avec cout et c comme arguments.

Finalement,

  • La valeur de retour de main est stockée dans EAX: 0. Cela est dû à la déclaration de return implicite. Vous pouvez également voir xorl rax rax au lieu de movl .
  • quitter et retourner au site d'appel. leave abréger cet épilogue et implicitement
    • Remplace le pointeur de la stack par le pointeur de base et
    • Ouvre le pointeur de base.

Après que cette opération et ret ont été effectuées, la trame a été effectivement effacée, même si l'appelant doit encore nettoyer les arguments pendant que nous utilisons la convention d'appel cdecl. D'autres conventions, par exemple stdcall, exigent que l'appelé soit rangé, par exemple en transmettant la quantité d'octets à ret .

Pointeur Omission

Il est également possible de ne pas utiliser de décalages à partir du pointeur base / image mais à partir du pointeur de stack (ESB). Cela rend le registre EBP qui contiendrait autrement la valeur du pointeur de trame disponible pour une utilisation arbitraire - mais il peut rendre le débogage impossible sur certaines machines et sera implicitement désactivé pour certaines fonctions . Il est particulièrement utile lors de la compilation pour les processeurs avec seulement quelques registres, y compris x86.

Cette optimisation est connue sous le nom d'omission de pointeur de trame (FPO) et est définie par -fomit-frame-pointer dans GCC et -Oy dans Clang; Notez qu'il est implicitement déclenché par chaque niveau d'optimisation> 0 si et seulement si le débogage est toujours possible, car il n'y a aucun coût à part cela. Pour plus d'informations, voir ici et ici .


1 Comme indiqué dans les commentaires, le pointeur de cadre est censé indiquer l'adresse après l'adresse de retour.

2 Notez que les registres qui commencent par R sont les contreparties 64 bits de celles qui commencent par E. EAX désigne les quatre octets de poids faible de RAX. J'ai utilisé les noms des registres 32 bits pour plus de clarté.

Parce que de toute évidence, la prochaine chose dont nous avons besoin est de travailler avec a et b, mais cela voudrait dire que le système d’exploitation / CPU (?) Doit d’abord sortir d et c pour revenir à a et b. Mais alors il se tirerait dans le pied car il a besoin de c et d dans la ligne suivante.

En bref:

Il n’y a pas besoin de faire éclater les arguments. Les arguments passés par l’appelant foo à la fonction doSomething et les variables locales dans doSomething peuvent tous être référencés comme un décalage par rapport au pointeur de base .
Alors,

  • Lorsqu’un appel de fonction est effectué, les arguments de la fonction sont PUSHed sur la stack. Ces arguments sont en outre référencés par le pointeur de base.
  • Lorsque la fonction retourne à son appelant, les arguments de la fonction de retour sont POPed de la stack en utilisant la méthode LIFO.

En détail:

La règle est que chaque appel de fonction entraîne la création d’un cadre de stack (le minimum étant l’adresse à retourner). Donc, si les appels funcB et funcB appellent funcC , trois frameworks de stack sont configurés les uns sur les autres. Lorsqu’une fonction retourne, son cadre devient invalide . Une fonction bien comscope n’agit que sur son propre frame de stack et n’empiète pas sur un autre. En d’autres termes, le POPing est exécuté sur le cadre de la stack en haut (lors du retour de la fonction).

entrer la description de l'image ici

La stack de votre question est configurée par l’appelant foo . Lorsque doSomething et doAnotherThing sont appelés, ils configurent leur propre stack. La figure peut vous aider à comprendre ceci:

entrer la description de l'image ici

Notez que, pour accéder aux arguments, le corps de la fonction devra descendre (adresses plus élevées) de l’emplacement où l’adresse de retour est stockée, et pour accéder aux variables locales, le corps de la fonction devra remonter la stack (adresses inférieures). ) par rapport à l’emplacement où l’adresse de retour est stockée . En fait, le code typique généré par le compilateur pour la fonction fera exactement cela. Le compilateur dédie un registre appelé EBP pour cela (Pointeur de base). Un autre nom pour la même chose est le pointeur d’image. En règle générale, le compilateur, en premier lieu pour le corps de la fonction, transmet la valeur EBP actuelle à la stack et définit l’EBP sur l’ESP en cours. Cela signifie qu’une fois que ceci est fait, dans n’importe quelle partie du code de fonction, l’argument 1 est EBP + 8 (4 octets pour chacun des EBP de l’appelant et l’adresse de retour), l’argument 2 est EBP + 12 (décimal), les variables locales sont EBP-4n loin.

 . . . [ebp - 4] (1st local variable) [ebp] (old ebp value) [ebp + 4] (return address) [ebp + 8] (1st argument) [ebp + 12] (2nd argument) [ebp + 16] (3rd function argument) 

Jetez un coup d’oeil au code C suivant pour la formation du frame de stack de la fonction:

 void MyFunction(int x, int y, int z) { int a, int b, int c; ... } 

Quand l’appelant l’appelle

 MyFunction(10, 5, 2); 

le code suivant sera généré

 ^ | call _MyFunction ; Equivalent to: | ; push eip + 2 | ; jmp _MyFunction | push 2 ; Push first argument | push 5 ; Push second argument | push 10 ; Push third argument 

et le code d’assemblage de la fonction sera (paramétré par appelé avant le retour)

 ^ | _MyFunction: | sub esp, 12 ; sizeof(a) + sizeof(b) + sizeof(c) | ;x = [ebp + 8], y = [ebp + 12], z = [ebp + 16] | ;a = [ebp - 4] = [esp + 8], b = [ebp - 8] = [esp + 4], c = [ebp - 12] = [esp] | mov ebp, esp | push ebp 

Les références:

  • Conventions d’appel de fonction et la stack .
  • Pointeur d’image et variables locales .
  • x86 Désassemblage / Fonctions et frameworks de stack .

Comme d’autres, il n’est pas nécessaire d’afficher les parameters jusqu’à ce qu’ils soient hors de scope.

Je vais coller un exemple de “Pointers and Memory” de Nick Parlante. Je pense que la situation est un peu plus simple que ce que vous aviez envisagé.

Voici le code:

 void X() { int a = 1; int b = 2; // T1 Y(a); // T3 Y(b); // T5 } void Y(int p) { int q; q = p + 2; // T2 (first time through), T4 (second time through) } 

Les points temporels T1, T2, etc sont marqués dans le code et l’état de la mémoire à ce moment-là est indiqué dans le dessin:

entrer la description de l'image ici

Différents processeurs et langages utilisent différentes conceptions de stacks. Deux modèles traditionnels à la fois sur le 8×86 et le 68000 sont appelés convention d’appel Pascal et convention d’appel C; chaque convention est gérée de la même manière dans les deux processeurs, à l’exception des noms des registres. Chacun utilise deux registres pour gérer la stack et les variables associées, appelées le pointeur de stack (SP ou A7) et le pointeur de cadre (BP ou A6).

Lorsque vous appelez une sous-routine en utilisant l’une des conventions, tous les parameters sont poussés sur la stack avant d’appeler la routine. Le code de la routine pousse ensuite la valeur actuelle du pointeur de trame sur la stack, copie la valeur actuelle du pointeur de stack sur le pointeur de trame et soustrait du pointeur de stack le nombre d’octets utilisés par les variables locales [le cas échéant]. Une fois cela fait, même si des données supplémentaires sont insérées dans la stack, toutes les variables locales seront stockées à des variables avec un déplacement négatif constant du pointeur de la stack, et tous les parameters qui ont été poussés sur la stack par l’appelant sont accessibles à un déplacement positif constant du pointeur de trame.

La différence entre les deux conventions réside dans la manière dont elles gèrent une sortie de sous-routine. Dans la convention C, la fonction de retour copie le pointeur de trame sur le pointeur de la stack [en la restaurant à la valeur immédiatement après la pression de l’ancien pointeur], affiche l’ancienne valeur du pointeur et effectue un retour. Tous les parameters que l’appelant avait mis sur la stack avant l’appel restront là. Dans la convention Pascal, après avoir sauté l’ancien pointeur de trame, le processeur affiche l’adresse de retour de la fonction, ajoute au pointeur de la stack le nombre d’octets de parameters poussés par l’appelant, puis passe à l’adresse de retour. Sur le 68000 d’origine, il était nécessaire d’utiliser une séquence à 3 instructions pour supprimer les parameters de l’appelant. les processeurs 8×86 et 680×0 après l’original incluaient une instruction “ret N” [ou 680×0] qui appendait N au pointeur de la stack lors d’un retour.

La convention Pascal a l’avantage de sauver un peu de code du côté de l’appelant, car l’appelant n’a pas besoin de mettre à jour le pointeur de stack après un appel de fonction. Cela nécessite toutefois que la fonction appelée sache exactement combien de parameters d’octets l’appelant va mettre sur la stack. Ne pas pousser le nombre correct de parameters sur la stack avant d’appeler une fonction qui utilise la convention de Pascal est presque garanti pour provoquer un plantage. Ceci est compensé par le fait qu’un petit code supplémentaire dans chaque méthode appelée va enregistrer le code aux endroits où la méthode est appelée. Pour cette raison, la plupart des routines d’origine de la boîte à outils Macintosh utilisaient la convention d’appel Pascal.

La convention d’appel C a l’avantage de permettre aux routines d’accepter un nombre variable de parameters, et d’être robuste même si une routine n’utilise pas tous les parameters transmis (l’appelant saura combien de parameters d’octets il a poussés, et sera donc en mesure de les nettoyer). De plus, il n’est pas nécessaire d’effectuer un nettoyage de stack après chaque appel de fonction. Si une routine appelle quatre fonctions en séquence, chacune utilisant des parameters de quatre octets, elle peut – au lieu d’utiliser un ADD SP,4 après chaque appel, utiliser un ADD SP,16 après le dernier appel pour nettoyer les parameters de les quatre appels.

De nos jours, les conventions d’appel décrites sont considérées comme quelque peu dépassées. Étant donné que les compilateurs sont devenus plus efficaces lors de l’utilisation des registres, il est fréquent que les méthodes acceptent quelques parameters dans les registres plutôt que d’exiger que tous les parameters soient insérés dans la stack. Si une méthode peut utiliser des registres pour contenir tous les parameters et les variables locales, il n’est pas nécessaire d’utiliser un pointeur de trame et il n’est donc pas nécessaire de sauvegarder et de restaurer l’ancienne. Cependant, il est parfois nécessaire d’utiliser les anciennes conventions d’appel lors de l’appel des bibliothèques liées pour les utiliser.

Il y a déjà de très bonnes réponses ici. Cependant, si vous êtes toujours préoccupé par le comportement LIFO de la stack, considérez-le comme une stack d’images, plutôt qu’une stack de variables. Ce que je veux dire, c’est que, même si une fonction accède à des variables qui ne sont pas au sumt de la stack, elle ne fonctionne que sur l’ élément en haut de la stack: un seul cadre de stack.

Bien sûr, il y a des exceptions à cela. Les variables locales de l’ensemble de la chaîne d’appels sont toujours allouées et disponibles. Mais ils ne seront pas directement accessibles. Au lieu de cela, ils sont passés par référence (ou par pointeur, ce qui n’est vraiment que sémantiquement différent). Dans ce cas, il est possible d’accéder à une variable locale d’une trame de stack beaucoup plus bas. Mais même dans ce cas, la fonction en cours d’exécution ne fonctionne toujours que sur ses propres données locales. Il accède à une référence stockée dans son propre frame de stack, ce qui peut faire référence à quelque chose sur le tas, dans la mémoire statique ou plus loin dans la stack.

C’est la partie de l’abstraction de la stack qui rend les fonctions appelables dans n’importe quel ordre et permet la récursivité. Le cadre de stack supérieur est le seul object directement accessible par le code. Tout le rest est accessible indirectement (via un pointeur qui vit dans le cadre de la stack supérieure).

Il pourrait être instructif de regarder l’assemblage de votre petit programme, surtout si vous comstackz sans optimisation. Je pense que vous verrez que tout l’access à la mémoire de votre fonction se fait par un décalage par rapport au pointeur de la stack, ce qui explique comment le compilateur écrit le code de la fonction. Dans le cas d’un passage par référence, vous verrez des instructions d’access indirectes à la mémoire via un pointeur stocké à un certain décalage du pointeur de trame de la stack.

La stack d’appels n’est pas une structure de données de stack. Dans les coulisses, les ordinateurs que nous utilisons sont des implémentations de l’architecture des machines à access aléatoire. Ainsi, a et b peuvent être directement accessibles.

Dans les coulisses, la machine fait:

  • get “a” est égal à la lecture de la valeur du quasortingème élément sous le sumt de la stack.
  • get “b” est égal à la lecture de la valeur du troisième élément sous le sumt de la stack.

http://en.wikipedia.org/wiki/Random-access_machine