Comment fonctionne la pile en langage assembleur?

(j'ai fait un gist de tout le code dans cette réponse au cas où vous voulez jouer avec elle)

j'ai seulement fait la plupart des choses basiques en asm pendant mon cours CS101 en 2003. Et je n'avais jamais vraiment "compris" comment asm et stack fonctionnent jusqu'à ce que je réalise que tout est basicaly comme programmation en C ou C++ ... mais sans variables locales, paramètres et fonctions. Cela ne semble probablement pas encore facile:) laissez-moi vous montrer (pour x86 asm avec Intel syntaxe ).

---

1. Qu'est-ce que la pile

Stack est un morceau contigu de mémoire alloué pour chaque thread quand il commence. Vous pouvez y stocker ce que vous voulez. Dans le langage C++ ( code snippet #1 ):

const int STACK_CAPACITY = 1000;
thread_local int stack[STACK_CAPACITY];

---

2. La pile du haut et du bas

en principe, vous pouvez stocker des valeurs dans des cellules aléatoires de stack tableau ( snippet # 2.1 ):

cin >> stack[333];
cin >> stack[517];
stack[555] = stack[333] + stack[517];

mais imaginez à quel point il serait difficile de se rappeler quelles cellules de stack sont déjà utilisées et lesquelles sont"libres". C'est pourquoi nous avons mis de nouvelles valeurs sur la pile à côté de l'autre.

une chose étrange à propos de la pile (x86) asm est que vous y ajoutez des choses à partir du dernier index et passer aux index inférieurs: stack[999], puis stack[998] et ainsi de suite ( snippet # 2.2 ):

cin >> stack[999];
cin >> stack[998];
stack[997] = stack[999] + stack[998];

et encore (coution, vous allez être confus maintenant) le nom" officiel "de stack[999] est bas de la pile .

La dernière cellule utilisée ( stack[997] dans l'exemple ci-dessus) est appelée haut de la pile (voir où le haut de la pile est sur x86 ).

---

3. Pointeur de pile (SP)

La pile

n'est pas la seule chose visible partout dans votre code asm. Vous pouvez également manipuler les registres CPU (voir registres à usage général ). Ils sont vraiment comme des variables globales:

int AX, BX, SP, BP, ...;
int main(){...}

il y a un registre CPU dédié (SP) pour garder la trace du dernier élément ajouté à la pile. Comme nom suggère qu'il est, bien, un pointeur (contient une adresse mémoire comme 0xAAAABBCC). Mais pour les fins de ce post, je vais l'utiliser comme un indice.

au début du fil SP == STACK_CAPACITY et ensuite vous le décrémentez en cas de besoin. La règle est que vous ne pouvez pas écrire à des cellules de pile au-delà du sommet de la pile et tout index moins que SP est invalide, donc vous d'abord décrément SP et ensuite écrivez une valeur à la cellule nouvellement attribuée.

quand vous savez que vous allez ajouter plusieurs valeurs sur la pile dans une rangée, vous pouvez réserver l'espace pour chacun d'eux à l'avance ( extrait #3 ):

SP -= 3;
cin >> stack[999];
cin >> stack[998];
stack[997] = stack[999] + stack[998];

Note. Maintenant vous pouvez voir pourquoi "affectation" sur la pile est si rapide. Vous n'attribuez pas réellement quoi que ce soit (comme dans new mot-clé ou malloc ), c'est juste un décrément entier simple.

---

4. Se débarrasser des variables locales

prenons cette fonction simpliste ( snippet # 4.1 ):

int triple(int a) {
    int result = a * 3;
    return result;
}

et réécrire sans variable locale ( snippet #4.2 ):

int triple_noLocals(int a) {
    SP -= 1; // move pointer to unused cell, where we can store what we need
    stack[SP] = a * 3;
    return stack[SP];
}

"1519570920 d'utilisation" ( extrait de #4.3 ):

// SP == 1000
someVar = triple_noLocals(11);
// now SP == 999, but we don't need the value at stack[999] anymore
// and we will move the stack index back, so we can reuse this cell later
SP += 1; // SP == 1000 again

---

5. Push / pop

L'ajout d'un nouvel élément au sommet de la pile est une opération si fréquente que les CPU ont une instruction spéciale à cet effet, push . Nous l'implorerons comme ceci ( snippet 5.1 ):

void push(int value) {
    --SP;
    stack[SP] = value;
}

de même, en prenant l'élément supérieur de la pile ( snippet 5.2 ):

void pop(int& result) {
    result = stack[SP];
    ++SP; // note that `pop` decreases stack's size
}

modèle d'utilisation courant pour le push/pop est temporairement l'économie d'une certaine valeur. Dire, nous avoir quelque chose d'utile dans la variable myVar et pour une raison quelconque, nous devons faire des calculs qui vont l'écraser ( snippet 5.3 ):

int myVar = ...;
push(myVar); // SP == 999
myVar += 10;
... // do something with new value in myVar
pop(myVar); // restore original value, SP == 1000

---

6. Suppression des paramètres

passons maintenant les paramètres en utilisant stack ( snippet #6 ):

int triple_noL_noParams() { // `a` is at index 999, SP == 999
    SP -= 1; // SP == 998, stack[SP + 1] == a
    stack[SP] = stack[SP + 1] * 3;
    return stack[SP];
}

int main(){
    push(11); // SP == 999
    assert(triple(11) == triple_noL_noParams());
    SP += 2; // cleanup 1 local and 1 parameter
}

---

7. Se débarrasser de return déclarations

valeur de retour dans le registre AX ( extrait #7 ):

void triple_noL_noP_noReturn() { // `a` at 998, SP == 998
    SP -= 1; // SP == 997

    stack[SP] = stack[SP + 1] * 3;
    AX = stack[SP];

    SP += 1; // finally we can cleanup locals right in the function body, SP == 998
}

void main(){
    ... // some code
    push(AX); // save AX in case there is something useful there, SP == 999
    push(11); // SP == 998
    triple_noL_noP_noReturn();
    assert(triple(11) == AX);
    SP += 1; // cleanup param
             // locals were cleaned up in the function body, so we don't need to do it here
    pop(AX); // restore AX
    ...
}

---

8. Stack base pointer (BP) (aussi connu sous le nom de frame pointer ) et stack frame

permet de prendre plus de fonction "avancée" et de la réécrire dans notre ASM-comme C++ ( extrait # 8.1 ):

int myAlgo(int a, int b) {
    int t1 = a * 3;
    int t2 = b * 3;
    return t1 - t2;
}

void myAlgo_noLPR() { // `a` at 997, `b` at 998, old AX at 999, SP == 997
    SP -= 2; // SP == 995

    stack[SP + 1] = stack[SP + 2] * 3; 
    stack[SP]     = stack[SP + 3] * 3;
    AX = stack[SP + 1] - stack[SP];

    SP += 2; // cleanup locals, SP == 997
}

int main(){
    push(AX); // SP == 999
    push(22); // SP == 998
    push(11); // SP == 997
    myAlgo_noLPR();
    assert(myAlgo(11, 22) == AX);
    SP += 2;
    pop(AX);
}

imaginez maintenant que nous avons décidé d'introduire une nouvelle variable locale pour stocker le résultat avant de revenir, comme nous le faisons dans tripple (snippet #4.1). Le corps de la fonction ( extrait de #8.2 ):

SP -= 3; // SP == 994
stack[SP + 2] = stack[SP + 3] * 3; 
stack[SP + 1] = stack[SP + 4] * 3;
stack[SP]     = stack[SP + 2] - stack[SP + 1];
AX = stack[SP];
SP += 3;

vous voyez, nous avons dû mettre à jour chaque référence aux paramètres de fonction et aux variables locales. Pour éviter cela, nous avons besoin d'un index ancre, qui ne changer lorsque la pile augmente.

nous allons créer l'ancre dès l'entrée de la fonction (avant d'allouer de l'espace pour les locaux) en sauvegardant le top courant (valeur de SP) dans le registre BP. extrait #8.3 :

void myAlgo_noLPR_withAnchor() { // `a` at 997, `b` at 998, SP == 997
    push(BP);   // save old BP, SP == 996
    BP = SP;    // create anchor, stack[BP] == old value of BP, now BP == 996
    SP -= 2;    // SP == 994

    stack[BP - 1] = stack[BP + 1] * 3;
    stack[BP - 2] = stack[BP + 2] * 3;
    AX = stack[BP - 1] - stack[BP - 2];

    SP = BP;    // cleanup locals, SP == 996
    pop(BP);    // SP == 997
}

la tranche de pile, qui appartient à et est en plein contrôle de la fonction est appelée stack frame de la fonction . Par exemple: myAlgo_noLPR_withAnchor 's stack frame is stack[996 .. 994] (les deux idexes inclusif.)

Le cadre commence à la BP de la fonction (après que nous l'ayons mis à jour à l'intérieur de la fonction) et dure jusqu'au prochain cadre de pile. Ainsi, les paramètres sur la pile font partie du cadre de la pile de l'appelant (voir la note 8a).

Notes:

8a. Wikipedia dit le contraire sur les paramètres, mais ici, j'adhère à Intel software developer's manual , voir vol. Un, section 6.2.4.1 pointeur de base du châssis de cheminée et Figure 6-2 dans la section 6.3.2 opération D'appel de distance et de retour . Les paramètres de la fonction et le cadre de la pile font partie de l'enregistrement d'activation de la fonction (voir la fonction de génération périlogues ).

8b. offsets positifs du point BP aux paramètres de fonction et les offsets négatifs pointent vers les variables locales. C'est assez pratique pour déboguer

8c. stack[BP] stocke l'adresse du cadre de pile précédent, stack[stack[BP]] stocke le cadre de pile pré-précédent et ainsi de suite. En suivant cette chaîne, vous pouvez découvrir les cadres de toutes les fonctions du programme, qui ne sont pas encore revenus. C'est ainsi que les débogueurs montrent que vous appelez la pile

8d. les 3 premières instructions de myAlgo_noLPR_withAnchor , où nous configurons le cadre (enregistrer Vieux BP, mise à jour BP, espace de réserve pour les locaux) sont appelés prologue de fonction

---

9. Conventions appelant

dans l'extrait 8.1 nous avons poussé les paramètres pour myAlgo de droite à gauche et nous avons retourné le résultat dans AX . Nous pourrions aussi bien passer par les params de gauche à droite et revenir dans BX . Ou passer params en BX et CX et revenir en AX. Évidemment, identification de l'appelant ( main() ) et appelé fonction doit convenir où et dans quel ordre toutes ces choses sont stockées.

convention d'Appel est un ensemble de règles sur la façon dont les paramètres sont passés et le résultat est retourné.

Dans le code ci-dessus, nous avons utilisé cdecl convention d'appel :

• les paramètres sont transmis sur la pile, avec le premier argument à l'adresse la plus basse sur la pile au moment de l'appel (poussé dernier <...>). L'appelant est responsable d'enlever les paramètres de la pile après l'appel.
• la valeur de retour est placée dans AX
• EBP et ESP doit être préservé par la callee ( myAlgo_noLPR_withAnchor fonction dans notre cas), de sorte que l'appelant ( main fonction) peut compter sur les registres n'ayant pas été changés par un appel.
• tous les autres registres (EAX, <...>) peuvent être librement modifié par le callee; si un appelant souhaite conserver une valeur avant et après l'appel de fonction, il doit sauvegarder la valeur ailleurs (nous le faisons avec AX)

^{(Source: exemple "cdecl 32 bits" de la Documentation de débordement de pile; copyright 2016 par icktoofay et Peter Cordes ; sous licence CC BY-SA 3.0. Une archive du contenu complet de la Documentation de débordement de la pile peut être trouvé à archive.org, dans lequel cet exemple est indexé par thème ID 3261 et exemple ID 11196.)}

---

10. Se débarrasser des appels de fonction

Maintenant, la partie la plus intéressante. Tout comme les données, le code exécutable est également stocké dans la mémoire (sans aucun rapport avec la mémoire pour la pile) et chaque instruction a une adresse.

Lorsqu'il n'est pas commandé sinon, le CPU exécute les instructions les unes après les autres, dans l'ordre où elles sont stockées en mémoire. Mais nous pouvons commander au CPU de "sauter" à un autre endroit dans la mémoire et d'exécuter des instructions à partir de là. En asm, il peut s'agir de n'importe quelle adresse, et dans les langages de haut niveau comme C++, vous ne pouvez sauter que sur des adresses marquées par des étiquettes ( il y a des solutions de rechange mais elles ne sont pas jolies, pour le moins).

prenons cette fonction ( extrait # 10.1 ):

int myAlgo_withCalls(int a, int b) {
    int t1 = triple(a);
    int t2 = triple(b);
    return t1 - t2;
}

et au lieu d'appeler tripple c++ way, faites ce qui suit:

1. copie tripple 's du corps à l'intérieur de myAlgo
2. à myAlgo entrée de sauter par-dessus tripple code avec goto
3. quand nous avons besoin d'exécuter le code de tripple , enregistrer sur l'adresse de la pile de la ligne de code juste après tripple appel, de sorte que nous pouvons revenir ici plus tard et continuer l'exécution ( PUSH_ADDRESS macro ci-dessous)
4. sautez à l'adresse de la fonction tripple et exécutez-la jusqu'à la fin (3. et 4. ensemble sont CALL macro)
5. à la fin du tripple (après avoir nettoyé les locaux), prendre l'adresse de retour du haut de la pile et sauter là ( RET macro)

parce qu'il n'y a pas de moyen facile de passer à un code particulier adresse en C++, Nous utiliserons des étiquettes pour marquer les lieux de sauts. Je ne vais pas entrer dans les détails comment les macros ci-dessous fonctionnent, juste croyez-moi ils font ce que je dis qu'ils font ( snippet # 10.2 ):

// pushes the address of the code at label's location on the stack
// NOTE1: this gonna work only with 32-bit compiler (so that pointer is 32-bit and fits in int)
// NOTE2: __asm block is specific for Visual C++. In GCC use https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
#define PUSH_ADDRESS(labelName) {               \
    void* tmpPointer;                           \
    __asm{ mov [tmpPointer], offset labelName } \
    push(reinterpret_cast<int>(tmpPointer));    \
}

// why we need indirection, read https://stackoverflow.com/a/13301627/264047
#define TOKENPASTE(x, y) x ## y
#define TOKENPASTE2(x, y) TOKENPASTE(x, y)

// generates token (not a string) we will use as label name. 
// Example: LABEL_NAME(155) will generate token `lbl_155`
#define LABEL_NAME(num) TOKENPASTE2(lbl_, num)

#define CALL_IMPL(funcLabelName, callId)    \
    PUSH_ADDRESS(LABEL_NAME(callId));       \
    goto funcLabelName;                     \
    LABEL_NAME(callId) :

// saves return address on the stack and jumps to label `funcLabelName`
#define CALL(funcLabelName) CALL_IMPL(funcLabelName, __LINE__)

// takes address at the top of stack and jump there
#define RET() {                                         \
    int tmpInt;                                         \
    pop(tmpInt);                                        \
    void* tmpPointer = reinterpret_cast<void*>(tmpInt); \
    __asm{ jmp tmpPointer }                             \
}

void myAlgo_asm() {
    goto my_algo_start;

triple_label:
    push(BP);
    BP = SP;
    SP -= 1;

    // stack[BP] == old BP, stack[BP + 1] == return address
    stack[BP - 1] = stack[BP + 2] * 3;
    AX = stack[BP - 1];

    SP = BP;     
    pop(BP);
    RET();

my_algo_start:
    push(BP);   // SP == 995
    BP = SP;    // BP == 995; stack[BP] == old BP, 
                // stack[BP + 1] == dummy return address, 
                // `a` at [BP + 2], `b` at [BP + 3]
    SP -= 2;    // SP == 993

    push(AX);
    push(stack[BP + 2]);
    CALL(triple_label);
    stack[BP - 1] = AX;
    SP -= 1;
    pop(AX);

    push(AX);
    push(stack[BP + 3]);
    CALL(triple_label);
    stack[BP - 2] = AX;
    SP -= 1;
    pop(AX);

    AX = stack[BP - 1] - stack[BP - 2];

    SP = BP; // cleanup locals, SP == 997
    pop(BP);
}

int main() {
    push(AX);
    push(22);
    push(11);
    push(7777); // dummy value, so that offsets inside function are like we've pushed return address
    myAlgo_asm();
    assert(myAlgo_withCalls(11, 22) == AX);
    SP += 1; // pop dummy "return address"
    SP += 2;
    pop(AX);
}

Notes:

10a. parce que l'adresse de retour est stockée sur la pile, en principe nous pouvons la changer. Voici comment attaque fracassante de pile fonctionne

10b. les 3 dernières instructions à la "fin" de triple_label (nettoyage locaux, restaurer la vieille BP, retour) sont appelés épilogue de la fonction

---

11. Assemblage

maintenant, regardons le vrai asm pour myAlgo_withCalls . Pour faire cela dans Visual Studio:

• jeu de construction de plate-forme x86
• type de construction: Debug
• définir le point de rupture quelque part à l'intérieur de myAlgo_withCalls
• , et lorsque l'exécution s'arrête au point d'arrêt, appuyez sur Ctrl + Alt + D

une différence avec notre ASM-like C++ est que la pile de asm fonctionne sur des octets plutôt que sur des ints. Ainsi, pour réserver l'espace pour un int , SP sera décrémenté de 4 octets.

Ici nous allons ( extrait de #11.1 , les numéros de ligne dans les commentaires sont du gist ):

;   114: int myAlgo_withCalls(int a, int b) {
 push        ebp        ; create stack frame 
 mov         ebp,esp  
; return address at (ebp + 4), `a` at (ebp + 8), `b` at (ebp + 12)

 sub         esp,0D8h   ; reserve space for locals. Compiler can reserve more bytes then needed. 0D8h is hexadecimal == 216 decimal 

 push        ebx        ; cdecl requires to save all these registers
 push        esi  
 push        edi  

 ; fill all the space for local variables (from (ebp-0D8h) to (ebp)) with value 0CCCCCCCCh repeated 36h times (36h * 4 == 0D8h)
 ; see /q/what-does-the-rep-stos-x86-assembly-instruction-sequence-do-42521/"lang-cpp prettyprint-override"> push        ebp  
 mov         ebp,esp  
 sub         esp,0CCh  
 push        ebx  
 push        esi  
 push        edi  
 lea         edi,[ebp-0CCh]  
 mov         ecx,33h  
 mov         eax,0CCCCCCCCh  
 rep stos    dword ptr es:[edi]  
 imul        eax,dword ptr [ebp+8],3  
 mov         dword ptr [ebp-8],eax  
 mov         eax,dword ptr [ebp-8]  
 pop         edi  
 pop         esi  
 pop         ebx  
 mov         esp,ebp  
 pop         ebp  
 ret  

l'Espoir, après la lecture de ce post, l'assemblée n'a pas l'air comme cryptique comme avant :)

---

Voici des liens à partir du corps du post et d'autres lectures:

• Eli Bendersky, Où le sommet de la pile est sur x86 - le haut/bas, push/pop, SP, la trame de pile, les conventions d'appel
• Eli Bendersky, Stack frame mise en page sur x86-64 - les arguments en passant sur x64, frame de pile, zone rouge
• de l'Université de Mariland, la Compréhension de la Pile - un vraiment bien écrit, introduction à la pile de concepts. (C'est pour MIPS (pas x86) et en syntaxe de gaz, mais c'est insignifiant pour le sujet). Voir les autres notes sur MIPS ISA Programming si intéressé.
• Asm x86 wikibook, Registres à Usage Général
• x86 Démontage wikibook, La Pile
• x86 Démontage wikibook, Fonctions et la Pile d'Images
• Intel Software developer's manuals - Je m'attendais à ce que ce soit vraiment hardcore, mais étonnamment, il est assez facile à lire (bien que la quantité d'informations est écrasante)
• Jonathan de Boyne Pollard, La gen sur la fonction perilogues - prologue et de l'épilogue, la trame de pile/activation de l'enregistrement, de la zone rouge