Comment fonctionne exactement la pile d'appels?

J'essaie de mieux comprendre comment fonctionnent les opérations de bas niveau des langages de programmation et en particulier comment ils interagissent avec le système d'exploitation / CPU. J'ai probablement lu toutes les réponses dans chaque thread lié à la pile / au tas ici sur Stack Overflow, et elles sont toutes brillantes. Mais il y a encore une chose que je n'ai pas encore entièrement comprise.

Considérez cette fonction dans un pseudo-code qui a tendance à ê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 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 pile, c'est qu'elle obéit strictement aux règles LIFO (dernier entré, premier sorti). Tout comme un type de données de pile en .NET, Java ou tout autre langage de programmation.

Mais si c'est le cas, que se passe-t-il après la ligne X? Parce que évidemment, la prochaine chose dont nous avons besoin est de travailler avec aet b, mais cela voudrait dire que le système d'exploitation / CPU (?) Doit apparaître det d' cabord revenir à aet b. Mais alors il se tirerait une balle dans le pied, car il en a besoin cet ddans la ligne suivante.

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

Une autre question connexe. Considérez que nous passons une référence à l'une des autres fonctions comme celle-ci:

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 la façon dont je comprends les choses, cela signifierait que les paramètres dans doSomethingindiquent essentiellement la même adresse mémoire comme aet bdans foo. Mais là encore, cela signifie qu'il n'y a pas de pop up de la pile jusqu'à ce que nous arrivions aet que cela seb produise.

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

La pile d'appels pourrait également être appelée une pile de cadres.
Les choses qui sont empilées après le principe LIFO ne sont pas les variables locales mais l'ensemble des cadres de pile ("appels") des fonctions appelées . Les variables locales sont poussées et sautées avec ces cadres respectivement dans le prologue et l' épilogue de fonction .

À l'intérieur du cadre, l'ordre des variables est totalement indéterminé; Les compilateurs "réorganisent" les positions des variables locales à l'intérieur d'une trame 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 tout au long de la durée de vie de la trame - il suffit donc de prendre une adresse d'ancrage, par exemple l'adresse de la trame elle-même, et de travailler avec des décalages de cette adresse pour les variables. Une telle adresse d'ancrage est en fait contenue dans le soi-disant pointeur de base ou de tramequi 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 ce que la pile d'appels typique est structurée comme ¹ :

Ajoutez le décalage d'une variable à laquelle nous voulons accéder à l'adresse contenue dans le pointeur de trame et nous obtenons l'adresse de notre variable. Donc, brièvement dit, le code y accède directement via des décalages constants au moment de la compilation à partir du pointeur de base; C'est 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 comprend les trois premières opérations:

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

Puis cinest déplacé dans le registre EDI ² et getest 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 d'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)dire que le décalage du pointeur de base est -1. Cet octet est notre variablec . Le décalage est négatif car la pile se développe vers le bas sur x86. L'opération suivante stocke cdans EAX: EAX est déplacé vers ESI, coutest déplacé vers EDI, puis l'opérateur d'insertion est appelé avec coutet cétant les arguments.

Finalement,

• La valeur de retour de mainest stockée dans EAX: 0. C'est à cause de l' returninstruction implicite . Vous pourriez également voir à la xorl rax raxplace de movl.
• quitter et revenir au site d'appel. leaveabrége cet épilogue et implicitement
  • Remplace le pointeur de pile par le pointeur de base et
  • Fait apparaître le pointeur de base.

Une fois cette opération reteffectuée, la trame a effectivement été sautée, bien que l'appelant doive toujours nettoyer les arguments car nous utilisons la convention d'appel cdecl. D'autres conventions, par exemple stdcall, obligent l'appelé à ranger, par exemple en passant le nombre d'octets à ret.

Omission du pointeur de trame

Il est également possible de ne pas utiliser les décalages à partir du pointeur de base / cadre mais à partir du pointeur de pile (ESB) à la place. Cela rend le registre EBP qui contiendrait autrement la valeur du pointeur de trame disponible pour une utilisation arbitraire - mais cela 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 des processeurs avec seulement quelques registres, y compris x86.

Cette optimisation est connue sous le nom de FPO (omission du pointeur de trame) et définie par -fomit-frame-pointerdans GCC et -Oydans 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'a aucun coût en dehors de cela. Pour plus d'informations, cliquez ici et ici .

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

² Notez que les registres commençant par R sont les équivalents 64 bits de ceux commençant 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 évidemment, 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 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 apparaître les arguments. Les arguments passés par l'appelant fooà la fonction doSomethinget 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 pile. 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 renvoyée sont POPed de la pile à l'aide de 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 pile (le minimum étant l'adresse à laquelle retourner). Ainsi, en cas d' funcAappels funcBet d' funcBappels funcC, trois cadres de pile sont mis en place les uns sur les autres. Lorsqu'une fonction revient, son cadre devient invalide . Une fonction bien comportée 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é vers le cadre de pile sur le dessus (lors du retour de la fonction).

La pile de votre question est configurée par l'appelant foo. Quand doSomethinget doAnotherThingsont appelés, ils créent leur propre pile. La figure peut vous aider à comprendre ceci:

Notez que, pour accéder aux arguments, le corps de la fonction devra traverser vers le bas (adresses supérieures) à 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 traverser la pile (adresses inférieures ) par rapport à l'emplacement où l'adresse de retour est stockée. En fait, le code généré par le compilateur typique pour la fonction fera exactement cela. Le compilateur dédie à cela un registre appelé EBP (Pointeur de base). Un autre nom pour le même est le pointeur de cadre. En règle générale, 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 sur l'ESP actuel. Cela signifie, une fois que cela 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 œil au code C suivant pour la formation du cadre de pile 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 (configuré par l'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
 

Références:

• Conventions d'appel de fonction et pile .
• Pointeur de trame et variables locales .
• Démontage / fonctions x86 et cadres de pile .

Comme d'autres l'ont noté, il n'est pas nécessaire de saisir les paramètres jusqu'à ce qu'ils soient hors de portée.

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 ce que vous imaginiez.

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é sur le dessin:

Différents processeurs et langages utilisent quelques conceptions de pile différentes. 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, à l'exception des 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 trame (BP ou A6).

Lors de l'appel d'un sous-programme en utilisant l'une ou l'autre convention, 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 vers 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 que cela est 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 à un déplacement positif constant à partir 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-programme. Dans la convention C, la fonction de retour copie le pointeur de cadre sur le pointeur de pile [le restaurant à la valeur qu'il avait juste après que l'ancien pointeur de cadre a été poussé], fait apparaître l'ancienne valeur du pointeur de cadre et effectue un retour. Tous les paramètres que l'appelant avait poussés sur la pile avant l'appel y resteront. Dans la convention Pascal, après avoir ouvert l'ancien pointeur de trame, le processeur affiche 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 passe à l'adresse de retour sautée. Sur le 68000 d'origine, 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 inclus un "ret N"

La convention Pascal a l'avantage d'économiser un peu de code du côté de l'appelant, puisque l'appelant n'a pas à mettre à jour le pointeur de pile après un appel de fonction. Cependant, il faut que la fonction appelée sache exactement combien d'octets de paramètres l'appelant va mettre sur la pile. Ne pas pousser le nombre approprié de paramètres sur la pile avant d'appeler une fonction qui utilise la convention Pascal est presque garanti pour provoquer un crash. Ceci est compensé, cependant, par le fait qu'un peu de code supplémentaire dans chaque méthode appelée enregistrera le code aux endroits où la méthode est appelée. Pour cette raison, la plupart des routines de la boîte à outils Macintosh d'origine utilisaient la convention d'appel Pascal.

La convention d'appel 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 qui sont passés (l'appelant saura combien d'octets de paramètres il a poussé, et pourra ainsi les nettoyer). De plus, il n'est pas nécessaire d'effectuer le nettoyage de la pile après chaque appel de fonction. Si une routine appelle quatre fonctions en séquence, dont chacune utilise quatre octets de paramètres, elle peut - au lieu d'utiliser un ADD SP,4après chaque appel, en utiliser une ADD SP,16aprè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. Puisque les compilateurs sont devenus plus efficaces dans l'utilisation des registres, il est courant que les méthodes acceptent quelques paramètres dans les 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 variables locales, il n'est pas nécessaire d'utiliser un pointeur de trame, et donc pas besoin de sauvegarder et de restaurer l'ancien. Pourtant, 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 pile, considérez-le comme une pile de cadres plutôt que comme une pile de variables. Ce que je veux dire, c'est que, même si une fonction peut accéder à des variables qui ne se trouvent pas en haut de la pile, elle ne fonctionne toujours que sur l' élément en haut de la pile: un cadre de pile unique.

Bien sûr, il y a des exceptions à cela. Les variables locales de toute la chaîne d'appels sont toujours allouées et disponibles. Mais ils ne seront pas accessibles directement. Au lieu de cela, ils sont passés par référence (ou par pointeur, ce qui n'est vraiment différent que sémantiquement). Dans ce cas, une variable locale d'un cadre de pile beaucoup plus bas est accessible. 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 cadre de pile, qui peut être une référence à quelque chose sur le tas, dans la mémoire statique ou plus bas dans la pile.

C'est la partie de l'abstraction de pile qui rend les fonctions appelables dans n'importe quel ordre et permet la récursivité. Le cadre supérieur de la pile est le seul objet auquel le code accède directement. Tout le reste est accessible indirectement (via un pointeur qui vit 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 tout l'accès à la mémoire dans votre fonction se produit via un décalage du pointeur de cadre de 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 verriez des instructions d'accès indirect à la mémoire via un pointeur qui est stocké à un certain décalage par rapport au pointeur de cadre de pile.

La pile d'appels n'est pas en fait une structure de données de pile. Dans les coulisses, les ordinateurs que nous utilisons sont des implémentations de l'architecture de la machine à accès aléatoire. Ainsi, a et b sont directement accessibles.

Dans les coulisses, la machine fait:

• get "a" équivaut à lire la valeur du quatrième élément sous le haut de la pile.
• get "b" équivaut à lire la valeur du troisième élément sous le haut de la pile.

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

Voici un diagramme que j'ai créé pour la pile d'appels de C. C'est plus précis et contemporain que les versions d'image Google

Et correspondant à la structure exacte du diagramme ci-dessus, voici un débogage de notepad.exe x64 sous Windows 7.

Les adresses basses et hautes sont permutées afin que la pile monte vers le haut dans ce diagramme. Le rouge indique le cadre exactement comme dans le premier diagramme (qui utilisait du rouge et du noir, mais le noir a maintenant été réutilisé); le noir est l'espace de la maison; le bleu est l'adresse de retour, qui est un décalage dans la fonction de l'appelant à l'instruction après l'appel; l'orange est l'alignement et le rose est l'endroit où le pointeur d'instruction pointe juste après l'appel et avant la première instruction. La valeur de retour homepace + est la plus petite trame autorisée sur les fenêtres et comme l'alignement rsp de 16 octets juste au début de la fonction appelée doit être conservé, cela inclut toujours un alignement de 8 octets.BaseThreadInitThunk etc.

Les cadres de fonction rouges décrivent ce que la fonction appelée «possède» logiquement + lit / modifie (il peut modifier un paramètre passé sur la pile qui était trop gros pour passer dans un registre sur -Ofast). Les lignes vertes délimitent l'espace que la fonction s'est alloué du début à la fin de la fonction.