Comment fonctionne exactement la pile d'appels ?

Question

J'essaie de mieux comprendre comment fonctionnent les opérations de bas niveau des langages de programmation et surtout comment ils interagissent avec l'OS/CPU. J'ai probablement lu toutes les réponses dans tous les fils de discussion relatifs aux piles et aux tas ici sur Stack Overflow, et elles sont toutes brillantes. Mais il y a encore une chose que je n'ai pas encore totalement comprise.

Considérez cette fonction en pseudo code qui tend à être du code Rust valide ;-)

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 pile doit ressembler à la ligne X :

Stack

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

Tout ce que j'ai lu sur le fonctionnement de la pile est qu'elle obéit strictement aux règles LIFO (dernier entré, premier sorti). Tout comme un type de données de pile dans .NET, Java ou tout autre langage de programmation.

Mais si c'est le cas, alors que se passe-t-il après la ligne X ? Parce qu'évidemment, la prochaine chose dont nous avons besoin est de travailler avec a y b mais cela signifierait que l'OS/CPU ( ?) doit être retiré. d y c d'abord pour revenir à a y b . Mais alors il se tirerait une balle dans le pied, parce qu'il faut c y d dans la ligne suivante.

Donc, je me demande ce que exactement se passe-t-il en 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 j'ai compris, cela signifierait que les paramètres de l'application doSomething pointent essentiellement vers la même adresse mémoire comme a y b en foo . Mais encore une fois, cela signifie qu'il n'y a pas remonter la pile jusqu'à ce qu'on arrive à a y b qui se passe.

Ces deux cas me font penser que je n'ai pas entièrement saisi comment exactement la pile fonctionne et comment elle suit strictement les LIFO règles.

Answer 1

La pile d'appels peut également être appelée pile de trames.
Les choses qui sont empilés après le principe LIFO ne sont pas les variables locales mais les cadres de pile entiers ("appels") des fonctions appelées . Les variables locales sont poussées et retirées en même temps que les cadres dans ce que l'on appelle les prologue de la fonction y épilogue respectivement.

À l'intérieur du cadre, l'ordre des variables n'est absolument pas spécifié ; Compilateurs "réordonner" les positions des variables locales à l'intérieur d'un cadre de manière appropriée pour optimiser leur alignement afin que le processeur puisse les récupérer le plus rapidement 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, disons l'adresse de la trame elle-même, et de travailler avec des décalages de cette adresse vers les variables. Une telle adresse d'ancrage est en fait contenue dans le fichier appelé base o pointeur de cadre qui est stocké dans le registre EBP. Les offsets, 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 la structure typique d'une pile d'appels 1 :

En ajoutant l'offset de la variable à laquelle nous voulons accéder à l'adresse contenue dans le pointeur de trame, nous obtenons l'adresse de notre variable. En bref, le code y accède directement par le biais de décalages constants au moment de la compilation à partir du pointeur de base ; il s'agit d'une simple arithmétique de pointeur.

Exemple

#include <iostream>

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<char, std::char_traits<char> >::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 prologue de la fonction est constitué des trois premières opérations :

• Le pointeur de base est poussé sur la pile.
• Le pointeur de pile est sauvegardé dans le pointeur de base.
• Le pointeur de pile est soustrait pour faire de la place aux variables locales.

Puis cin est déplacé dans le registre EDI 2 y get est appelé ; la valeur de retour est dans EAX.

Jusqu'à présent, tout va bien. Maintenant, la chose intéressante arrive :

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 -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 pile croît vers le bas sur x86. L'opération suivante stocke c dans EAX : EAX est déplacé vers ESI, cout est déplacé vers l'EDI et ensuite l'opérateur d'insertion est appelé avec cout y c étant les arguments.

Enfin,

• La valeur de retour de main est stocké dans EAX : 0. C'est à cause de l'implicite return déclaration. Vous pouvez également voir xorl rax rax au lieu de movl .
• quitter et revenir sur le lieu de l'appel. leave abrège cet épilogue et implicitement
  • Remplace le pointeur de pile par le pointeur de base et
  • Fait sauter le pointeur de base.

Après cette opération et ret ont été effectuées, le cadre a effectivement été retiré, bien que l'appelant doive encore nettoyer les arguments puisque nous utilisons la convention d'appel cdecl. D'autres conventions, comme stdcall, demandent à l'appelant de faire le ménage, par exemple en passant la quantité d'octets à ret .

Omission de pointeur de trame

Il est également possible de ne pas utiliser les décalages du pointeur de base/trame mais du pointeur de pile (ESB). Cela rend le registre EBP, qui contiendrait autrement la valeur du pointeur de trame, disponible pour une utilisation arbitraire - mais cela peut rendre l'utilisation de l'ESB plus difficile. débogage impossible sur certaines machines et sera implicitement désactivé pour certaines fonctions . Elle est particulièrement utile lors de la compilation pour les processeurs ne possédant que peu de registres, y compris les x86.

Cette optimisation est connue sous le nom de FPO (frame pointer omission) et définie par -fomit-frame-pointer dans le CCG 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 encore possible, puisqu'il n'a aucun coût à part cela. Pour plus d'informations, voir aquí y aquí .

---

1 Comme indiqué dans les commentaires, le pointeur de trame est vraisemblablement censé pointer vers l'adresse après l'adresse de retour.

2 Notez que les registres qui commencent par R sont les équivalents 64 bits de ceux 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é.

Answer 2

Parce qu'évidemment, la prochaine chose dont nous avons besoin est de travailler avec a et b, mais cela signifie que l'OS/CPU ( ?) doit d'abord faire sortir d et c pour revenir à a et b. Mais il se tirerait alors une balle dans le pied parce qu'il a besoin de c et d dans la ligne suivante.

En bref :

Il n'est pas nécessaire de faire sauter 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 en tant que décalage par rapport à l'élément pointeur de base .
Donc,

• Lorsqu'un appel de fonction est effectué, les arguments de la fonction sont PUSHÉS sur la pile. Ces arguments sont ensuite référencés par le pointeur de base.
• Lorsque la fonction retourne à son appelant, les arguments de la fonction de retour sont POP de la pile en utilisant la méthode LIFO.

---

En détail :

La règle est la suivante chaque appel de fonction entraîne la création d'un cadre de pile (le minimum étant l'adresse de retour). Ainsi, si funcA appelle funcB y funcB appelle funcC trois cadres d'empilage sont placés l'un au-dessus de l'autre. Lorsqu'une fonction revient, son cadre devient invalide. . Une fonction qui se comporte bien n'agit que sur son propre cadre de pile et n'empiète pas sur celui d'une autre. En d'autres termes, le POPing est effectué sur le cadre de pile du haut (au retour de la fonction).

La pile dans votre question est configurée par l'appelant. foo . Quand doSomething y doAnotherThing sont appelés, puis ils mettent en place leur propre pile. La figure suivante peut vous aider à comprendre cela :

Notez que, pour accéder aux arguments, le corps de la fonction devra se déplacer vers le bas (adresses plus élevées) à partir de l'emplacement où l'adresse de retour est stockée, et pour accéder aux variables locales, le corps de la fonction devra se déplacer vers le haut de la pile (adresses plus basses) 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 à cet effet (Base Pointer). Un autre nom pour le même est frame pointer. En général, le compilateur, en tant que première chose pour le corps de la fonction, pousse la valeur EBP actuelle sur la pile et définit l'EBP à l'ESP actuel. Cela signifie qu'une fois que cela est fait, dans n'importe quelle partie du code de la fonction, l'argument 1 est à EBP+8 (4 octets pour l'EBP de l'appelant et l'adresse de retour), l'argument 2 est à EBP+12 (décimal), les variables locales sont à EBP-4n.

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

Regardez le code C suivant pour la formation du cadre de la pile de la fonction :

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

Lorsque 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 (mis en place par le demandeur 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

---

Références :

• Conventions d'appel de fonction et la pile .
• Pointeur de trame et variables locales .
• Désassemblage x86/Fonctions et cadres de pile .

Answer 3

Comme d'autres l'ont fait remarquer, il n'est pas nécessaire de faire sauter les paramètres, jusqu'à ce qu'ils sortent du champ d'application.

Je vais coller quelques exemples tirés de "Pointers and Memory" de Nick Parlante. Je pense que la situation est un peu plus simple que vous ne l'imaginez.

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 dans le temps T1, T2, etc . sont marqués dans le code et l'état de la mémoire à ce moment-là est indiqué dans le dessin :

Answer 4

Les différents processeurs et langages utilisent quelques modèles de pile différents. Deux modèles traditionnels sur le 8x86 et le 68000 sont appelés la convention d'appel Pascal et la convention d'appel C ; chaque convention est gérée de la même manière dans les deux processeurs, sauf pour les noms des registres. Chacun utilise deux registres pour gérer la pile et les variables associées, appelés le pointeur de pile (SP ou A7) et le pointeur de cadre (BP ou A6).

Lorsque l'on appelle une sous-routine en utilisant l'une ou l'autre de ces conventions, tous les paramètres sont poussés sur la pile avant d'appeler la routine. Le code de la routine pousse ensuite la valeur actuelle du pointeur de trame sur la pile, copie la valeur actuelle du pointeur de pile sur le pointeur de trame et soustrait du pointeur de pile 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 poussées sur la pile, toutes les variables locales seront stockées dans des variables avec un déplacement négatif constant du pointeur de pile, et tous les paramètres qui ont été poussés sur la pile par l'appelant peuvent être accédés avec un déplacement positif constant du pointeur de cadre.

La différence entre les deux conventions réside dans la façon dont elles gèrent la sortie d'un sous-programme. Dans la convention C, la fonction de retour copie le pointeur de trame sur le pointeur de pile [le restaurant à la valeur qu'il avait juste après que l'ancien pointeur de trame ait été poussé], ouvre l'ancienne valeur du pointeur de trame, et effectue un retour. Tout paramètre que l'appelant avait placé sur la pile avant l'appel y restera. Dans la convention Pascal, après avoir sorti l'ancien pointeur de cadre, le processeur sort l'adresse de retour de la fonction, ajoute au pointeur de pile le nombre d'octets de paramètres poussés par l'appelant, puis va à l'adresse de retour sortie. Sur le 68000 original, il était nécessaire d'utiliser une séquence de 3 instructions pour supprimer les paramètres de l'appelant ; le 8x86 et tous les processeurs 680x0 après l'original incluaient une instruction "ret N" [ou équivalent 680x0] qui ajoutait N au pointeur de pile lors d'un retour.

La convention Pascal a l'avantage d'économiser un peu de code du côté de l'appelant, puisque ce dernier n'a pas à mettre à jour le pointeur de pile après un appel de fonction. Elle exige toutefois que la fonction appelée sache exactement combien d'octets de paramètres l'appelant va placer sur la pile. Si l'on ne parvient pas à placer le nombre approprié de paramètres sur la pile avant d'appeler une fonction qui utilise la convention Pascal, il est presque certain que cela provoquera un crash. Ceci est toutefois compensé par le fait qu'un peu de code supplémentaire dans chaque méthode appelée permettra d'économiser du code aux endroits où la méthode est appelée. Pour cette raison, la plupart des routines originales de la boîte à outils du Macintosh utilisaient la convention d'appel Pascal.

La convention d'appel du C a l'avantage de permettre aux routines d'accepter un nombre variable de paramètres, et d'être robuste même si une routine n'utilise pas tous les paramètres passés (l'appelant saura combien d'octets de paramètres il a poussé, et sera donc capable de les nettoyer). De plus, il n'est pas nécessaire de procéder au nettoyage de la pile après chaque appel de fonction. Si une routine appelle quatre fonctions en séquence, chacune d'entre elles utilisant des paramètres de quatre octets, elle peut - au lieu d'utiliser une fonction de type ADD SP,4 après chaque appel, utilisez un ADD SP,16 après le dernier appel pour nettoyer les paramètres des quatre appels.

De nos jours, les conventions d'appel décrites sont considérées comme quelque peu désuètes. Depuis que les compilateurs sont devenus plus efficaces dans l'utilisation des registres, il est courant que les méthodes acceptent quelques paramètres dans des registres plutôt que d'exiger que tous les paramètres soient poussés sur la pile ; si une méthode peut utiliser des registres pour contenir tous les paramètres et les variables locales, il n'y a pas besoin d'utiliser un frame pointer, et donc pas besoin de sauvegarder et restaurer l'ancien. Néanmoins, il est parfois nécessaire d'utiliser les anciennes conventions d'appel pour appeler des bibliothèques qui ont été liées pour les utiliser.

Answer 5

Il y a déjà de très bonnes réponses ici. Toutefois, si vous êtes toujours préoccupé par le comportement LIFO de la pile, considérez-la comme une pile de cadres, plutôt que comme une pile de variables. Ce que je veux dire, c'est que, bien qu'une fonction puisse accéder à des variables qui ne sont pas en haut de la pile, elle n'opère toujours que sur la pile de cadres. item au sommet de la pile : un seul cadre de pile.

Bien sûr, il y a des exceptions à cette règle. Les variables locales de l'ensemble de la chaîne d'appel sont toujours allouées et disponibles. Mais on ne pourra pas y accéder directement. Au lieu de cela, elles sont transmises par référence (ou par pointeur, ce qui n'est vraiment différent que sémantiquement). Dans ce cas, on peut accéder à une variable locale d'un cadre de pile situé beaucoup plus bas. Mais même dans ce cas, la fonction en cours d'exécution n'agit que sur ses propres données locales. Il accède à une référence stockée dans son propre cadre de pile, qui peut être une référence à quelque chose sur le tas, dans la mémoire statique, ou plus loin sur la pile.

C'est la partie de l'abstraction de la pile qui rend les fonctions appelables dans n'importe quel ordre et permet la récursion. Le cadre supérieur de la pile est le seul objet auquel le code accède directement. Tout le reste est accessible indirectement (par un pointeur qui se trouve dans le cadre supérieur de la pile).

Il peut être instructif de regarder l'assemblage de votre petit programme, surtout si vous compilez sans optimisation. Je pense que vous verrez que tous les accès à la mémoire dans votre fonction se font par le biais d'un décalage du pointeur du cadre de la pile, qui est la façon dont le code de la fonction sera écrit par le compilateur. Dans le cas d'un passage par référence, vous verrez des instructions d'accès indirect à la mémoire par le biais d'un pointeur stocké à un certain décalage du pointeur de cadre de pile.