View
32
Download
0
Category
Preview:
DESCRIPTION
La pile. Laurent JEANPIERRE D’après le cours de Pascal FOUGERAY IUT de CAEN – Campus 3. Contenu du cours. Définition Manipulations Appel de fonctions Gestion du résultat Gestion des variables Gestion des paramètres Exemple : Fibonacci Conclusion. - PowerPoint PPT Presentation
Citation preview
Département Informatique
La pile
Laurent JEANPIERRE <jeanpl@iutc3.unicaen.fr>
D’après le cours de Pascal FOUGERAY
IUT de CAEN – Campus 3
Département Informatique 2
Contenu du cours
Définition
Manipulations
Appel de fonctions
Gestion du résultat
Gestion des variables
Gestion des paramètres
Exemple : Fibonacci
Conclusion
Département Informatique 3
Définition de la pile (stack)
Structure de donnéesStratégie LIFO
Last In First OutDernier entré, premier sortiAnalogie avec pile d’assiettes.
Mémoire de stockageTemporaireStockage bien parenthésé
[({}{}{})()({})][]
Département Informatique 4
La pile en mémoire
Zone de mémoire séparéeRegistre de segment spécifique
SS = Stack SegmentRegistre de position spécifique
eSP = (extended) Stack Pointerss:esp indique la dernière valeur empilée
Sur x86, elle croît à l’envers… Sommet_pile ≤ Base_pile
Département Informatique 5
Contenu du cours
Définition
Manipulations
Appel de fonctions
Gestion du résultat
Gestion des variables
Gestion des paramètres
Exemple : Fibonacci
Conclusion
Département Informatique 6
Manipulations de la pile
Trois possibilités : Modification de eSP
movl %ebp,%esp # ebp esp addl $4,%esp # esp esp+4
Accès direct à la mémoire (voir cours sur modes d’adressage) movw 4(%esp), %ax # mem[esp+4] ax
Instructions spécifiques pushw, pushl popw, popl
Département Informatique 7
Instructions spécifiques PUSH = empiler
Met une valeur sur la pile. Le registre esp diminue de la taille spécifiée L’opérande est stockée à l’adresse (%esp)
POP = dépiler Retire une valeur de la pile. L’opérande est remplie avec le contenu
de l’adresse (%esp) Le registre esp augmente de la taille spécifiée
Spécificité : Pas d’opération sur 1 octet (processeur 16 bits)
Département Informatique 8
Exemple de manipulation de pile (1)
movl $0,%eaxpushl $0x01234567pushw $0x89ABpushw $0xCDEFmovb (%esp),%alpopl %ebxmovw %ax,1(%esp)popl %eax
Département Informatique 9
esp
Exemple de manipulation de pile (2)
movl $0,%eaxpushl $0x01234567pushw $0x89AB
Registres
EAX EBX ESP
******** ???????? 10010
Pile
00000000
Département Informatique 10
esp
Exemple de manipulation de pile (2)
movl $0,%eaxpushl $0x01234567pushw $0x89AB
Registres
EAX EBX ESP
00000000 ???????? 10010
Pile
9610
esp0123
4567
Département Informatique 11
esp
Exemple de manipulation de pile (2)
pushl $0x01234567pushw $0x89ABpushw $0xCDEF
Registres
EAX EBX ESP
00000000 ???????? 9610
Pile
esp
0123
4567
89AB
9410
Département Informatique 12
esp
Exemple de manipulation de pile (2)
pushw $0x89ABpushw $0xCDEFmovb (esp),%al
Registres
EAX EBX ESP
00000000 ???????? 9410
Pile
esp
0123
4567
89AB
9210
CDEF
Département Informatique 13
esp
Exemple de manipulation de pile (2)
pushw $0xCDEFmovb (%esp),%alpopl %ebx
Registres
EAX EBX ESP
00000000 ???????? 9210
Pile0123
4567
89AB
CDEF
000000EF
Département Informatique 14
esp
Exemple de manipulation de pile (2)
movb (esp),%alpopl %ebxmovw %ax, 1(%esp)
Registres
EAX EBX ESP
000000EF ???????? 9210
Pile
esp
0123
4567
89AB
9610
CDEF
89ABCDEF
Département Informatique 15
esp
Exemple de manipulation de pile (2)
popl %ebxmovw %ax, 1(%esp)popl %eax
Registres
EAX EBX ESP
000000EF 89ABCDEF 9610
Pile0123
4567
89AB
CDEF
0100
EF67
Département Informatique 16
Exemple de manipulation de pile (2)
popl %ebxmovw %ax,1(%esp)popl %eax
Registres
EAX EBX ESP
000000EF 89ABCDEF 9610
Pile0100
EF67
89AB
CDEF
esp
esp
100100100EF67
Département Informatique 17
Contenu du cours
Définition
Manipulations
Appel de fonctions
Gestion du résultat
Gestion des variables
Gestion des paramètres
Exemple : Fibonacci
Conclusion
Département Informatique 18
Appel de fonctions
Programme structuré fonctionsExemple :
Fonction déplacer(Object o) Soulever(o) SeDéplacer() Poser(o)Fin
Fonctions blocs bien parenthésés Utilisation naturelle de la pile
Département Informatique 19
Appel de fonctions en assembleur
Instruction : call <label>Empile EIP (compteur ordinal)EIP label
La fonction s’exécute…
Instruction : retDépile EIP
Le programme principal reprend…
Département Informatique 20
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
2 1003
3
969
Département Informatique 21
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
9 9610
3
Département Informatique 22
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
10 963
3
100
Département Informatique 23
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
3 1006
3
96
4
Département Informatique 24
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
6 967
4
Département Informatique 25
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
7 9615
4
92
8
Département Informatique 26
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
15 9216
4
8
Département Informatique 27
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
16 928
4
96
8
Département Informatique 28
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
8 964
4
100
8
Département Informatique 29
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
4 10013
4
96
5
8
Département Informatique 30
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
13 9614
5
8
Département Informatique 31
Appel de fonctions : exemple
1. Deplacer:
2. call Soulever
3. call Bouger
4. call Poser
5. ret
6. Bouger:
7. call Marcher
8. ret
9. Soulever: …
10. ret
11. Bouger: …
12. ret
13. Poser: …
14. ret
15. Marcher:…
16. ret
EIP ESP
14 965
5
100
8
Département Informatique 32
Contenu du cours
Définition
Manipulations
Appel de fonctions
Gestion du résultat
Gestion des variables
Gestion des paramètres
Exemple : Fibonacci
Conclusion
Département Informatique 33
Le résultat de la fonction (1)
Convention du langage C :
Le résultat est renvoyé dans EAXParfait pour des entiers ou des adresses Inadapté pour le reste
Le résultat est stocké temporairement Dans une pseudo-variable localeDans la dernière variable allouée
Département Informatique 34
Le résultat de la fonction (2)
Valeurs plus petites (char, short)Extension à 32 bits.Attention au signe ! (unsigned char ≠ char)
Valeurs plus grandesPar adresse (pointeur dans eax)Cas des structures très délicat.
Valeurs flottantes (float, single, double)Dans st(0) (pile FPU, voir cours sur la FPU)
Département Informatique 35
Contenu du cours
Définition
Manipulations
Appel de fonctions
Gestion du résultat
Gestion des variables
Gestion des paramètres
Exemple : Fibonacci
Conclusion
Département Informatique 36
Les variables
Une fonction peut avoir des variables…int main() { int a = 3; int b = a+5;}
A et B sont locales à la fonction mainComment les mémoriser ?
Sur le tasSur la pile
Département Informatique 37
Variables globales : le tas
.dataa: .long 3b: .long 0
.textmain:
movl (a), %eaxaddl $5, %eaxmovl %eax, (b)ret
Très bien pour les variables globales… Mais pour les fonctions récursives ?
Département Informatique 38
Fonctions récursives
Définition :Une fonction est dite « récursive » si elle
s’appelle elle-même, ou si elle utilise une autre fonction qui l’appelle (la 1ère).
Exemple : la suite de fibonacciFibo(0) = 0Fibo(1) = 1Fibo(n) = Fibo(n-1) + Fibo(n-2) n≥20 1 1 2 3 5 8 13 21 34 55 89 …
Département Informatique 39
Exemple2 : Fibonacci
int Fibo(int n){int a,b;if (n==0) return 0;if (n==1) return 1;a = Fibo(n-1);b = Fibo(n-2);return a+b;
} Chaque appel de Fibo a des valeurs de a et de b
différentes… Impossible donc de les stocker en mémoire…
Département Informatique 40
Variables locales : la pile
La pile offre une mémoire ContextuelleSelon des blocs parenthésés Il suffit d’y stocker les variables locales
Problème :ESP varie sans cesse…Comment retrouver les variables ?
Solution :Le cadre de pile
Département Informatique 41
Cadre de pile (ébauche)
Utilisation du registre EBP : Mémorise la base de la pile
pour la fonction active Accès direct aux variables via EBP
Un registre EBP pour chaque fonction Sauvegarde de la valeur précédente… Sur la pile !
Chaque fonction commence donc par : Sauvegarde EBP Allocation du cadre de pile
Département Informatique 42
Contenu du cours
Définition
Manipulations
Appel de fonctions
Gestion du résultat
Gestion des variables
Gestion des paramètres
Exemple : Fibonacci
Conclusion
Département Informatique 43
Les paramètres des fonctions
Une fonction peut avoir des paramètresprintf ("hello %s!","World");
Un paramètre = une variable initialisée… Géré comme une variable locale
Mais Initialisé par l’appelantA ce moment, pas encore de cadre de pile Position particulière dans le FUTUR
cadre de pile
Département Informatique 44
Cadre de pile (complet)
Le cadre de pile contient donc : Paramètres de fonction
Par l’appelant
Adresse de retour Automatique (call)
Sauvegarde EBP pushl %ebp movl %esp, %ebp
Variables Locales subl $taille,%esp
Paramètres(taille ?)
@ retour (32b)
Svg EBP (32b)
Var. Locales(taille ?)
ebp
esp
Département Informatique 45
Note spécifique 386 et plus…
La pile est alignée sur 32 bits… Convention logicielle de gcc (et autres…) Pas de justification matérielle
Tout paramètre prend n*32 bits ! int/void* 32 bits ok char/short 8/16 bits problème
extension du signe ou bourrage si non signé création de variables locales de la bonne taille
float/single 32 bits ok double 64 bits ok
On ne s’intéressera qu’aux multiples de 32 bits Reste Pas au programme
Département Informatique 46
Contenu du cours
Définition
Manipulations
Appel de fonctions
Gestion du résultat
Gestion des variables
Gestion des paramètres
Exemple : Fibonacci
Conclusion
Département Informatique 47
Fibonacci, le résultat final (1) int fibo(int n)
Locales : int a,b,r;
_fibo:# sauvegarde EBPpushl %ebp# EBP <- ESPmovl %esp, %ebp# Alloue 16 octets # sur la pilesubl $16, %esp
n (int)
@retour
EBP0
a (int)
b (int)
r (int)
* (32b)
ebp
esp
Paramètres
Contexte
Variables locales
Spécial
Département Informatique 48
Fibonacci, le résultat final (2)# if n==0cmpl $0, 8(%ebp) # compare 0 et n (EBP+8)jne L10 # saute si différentmovl $0, -12(%ebp) # mets 0 dans r (EBP-12)jmp L9 # saute à fin
L10:
# if n==1cmpl $1, 8(%ebp) # compare 1 et n (EBP+8)jne L11 # saute si différentmovl $1, -12(%ebp) # mets 1 dans r (EBP-12)jmp L9 # saute à fin
L11:
Département Informatique 49
Fibonacci, le résultat final (3)# a = fibo(n-1)movl 8(%ebp), %eax # eax <- n (EBP+8)decl %eax # eax <- eax-1movl %eax, (%esp) # (ESP+0) <- eax
# {Paramètre1 <- n-1}call _fibo # appelle fibo
# {résultat dans eax}movl %eax, -4(%ebp) # mets eax dans a (EBP-4)
# b = fibo(n-2)movl 8(%ebp), %eax # eax <- n (EBP+8)subl $2, %eax # eax <- eax-2movl %eax, (%esp) # (ESP+0) <- eax
# {Paramètre1 = n-2}call _fibo # appelle fibo {reseax} movl %eax, -8(%ebp) # mets eax dans b (EBP-8)
Département Informatique 50
Fibonacci, le résultat final (4)# r = a+bmovl -8(%ebp), %eax # eax <- b (EBP-8)addl -4(%ebp), %eax # eax <- eax + a (EBP-4)movl %eax, -12(%ebp) # mets eax dans r (EBP-12)
L9:movl -12(%ebp), %eax # eax <- r=(EBP+12)movl %ebp, %esp # %esp <- %ebppopl %ebp # Restaure ebpret # fin
Ou encore… (autre solution)L9:
movl -12(%ebp), %eax # eax <- r=(EBP+12)leave # Restaure le cadre de pileret # fin
Département Informatique 51
Contenu du cours
Définition
Manipulations
Appel de fonctions
Gestion du résultat
Gestion des variables
Gestion des paramètres
Exemple : Fibonacci
Conclusion
Département Informatique 52
Conclusion
La pile est un élément essentiel Sur TOUS les processeurs
Du plus petit (microcontrôleur spécialisé) Au plus gros (serveur de calculs)
Gestion identique Empile, Dépile, Registre « pointeur de pile » Notion de cadre de pile (avec des variantes)
Maîtriser la pile (et le tas) permet de Comprendre les « segmentation faults » Eviter les « core dump »
Recommended