La pile

Département Informatique

La pile

Laurent JEANPIERRE <[email protected]>

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é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é

[({}{}{})()({})][]


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


Contenu du cours

Définition

Manipulations

Appel de fonctions




Exemple : Fibonacci

Conclusion


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


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)


Exemple de manipulation de pile (1)

movl $0,%eaxpushl $0x01234567pushw $0x89ABpushw $0xCDEFmovb (%esp),%alpopl %ebxmovw %ax,1(%esp)popl %eax


esp


movl $0,%eaxpushl $0x01234567pushw $0x89AB

Registres

EAX EBX ESP

******** ???????? 10010

Pile

00000000


esp


movl $0,%eaxpushl $0x01234567pushw $0x89AB

Registres

EAX EBX ESP

00000000 ???????? 10010

Pile

9610

esp0123

4567


esp


pushl $0x01234567pushw $0x89ABpushw $0xCDEF

Registres

EAX EBX ESP

00000000 ???????? 9610

Pile

esp

0123

4567

89AB

9410


esp


pushw $0x89ABpushw $0xCDEFmovb (esp),%al

Registres

EAX EBX ESP

00000000 ???????? 9410

Pile

esp

0123

4567

89AB

9210

CDEF


esp


pushw $0xCDEFmovb (%esp),%alpopl %ebx

Registres

EAX EBX ESP

00000000 ???????? 9210

Pile0123

4567

89AB

CDEF

000000EF


esp


movb (esp),%alpopl %ebxmovw %ax, 1(%esp)

Registres

EAX EBX ESP

000000EF ???????? 9210

Pile

esp

0123

4567

89AB

9610

CDEF

89ABCDEF


esp


popl %ebxmovw %ax, 1(%esp)popl %eax

Registres

EAX EBX ESP

000000EF 89ABCDEF 9610

Pile0123

4567

89AB

CDEF

0100

EF67



popl %ebxmovw %ax,1(%esp)popl %eax

Registres

EAX EBX ESP

000000EF 89ABCDEF 9610

Pile0100

EF67

89AB

CDEF

esp

esp

100100100EF67


Contenu du cours

Définition

Manipulations

Appel de fonctions




Exemple : Fibonacci

Conclusion


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


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…


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



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



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



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



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



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



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



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



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



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



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



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


Contenu du cours

Définition

Manipulations

Appel de fonctions




Exemple : Fibonacci

Conclusion


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


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)


Contenu du cours

Définition

Manipulations

Appel de fonctions




Exemple : Fibonacci

Conclusion


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


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 ?


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 …


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…


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


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


Contenu du cours

Définition

Manipulations

Appel de fonctions




Exemple : Fibonacci

Conclusion


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


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


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


Contenu du cours

Définition

Manipulations

Appel de fonctions




Exemple : Fibonacci

Conclusion


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


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:


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)


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


Contenu du cours

Définition

Manipulations

Appel de fonctions




Exemple : Fibonacci

Conclusion


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 »

Documents

La pile