LdB Seance 8

De Ensiwiki
Aller à : navigation, rechercher
AttentionCette page est maintenue uniquement par les enseignants. Afin de ne pas perturber le déroulement des cours, elle n'a pas vocation à être modifiée par les élèves. Mais si vous avez des modifications à proposer, merci d'en discuter ou d'envoyer un e-mail aux auteurs de la page (cf. historique)

Laptop.png  Première Année  CDROM.png  Informatique 

Introduction

Le but de cette séance est de comprendre les conventions de gestion des registres et de la mémoire lors de l'exécution de programmes assembleur, ce qui leur permettra d'interagir avec des fonctions écrites en C.

On touche dans cette séance à des aspects fondamentaux du système (e.g. convention de gestion de la pile d'exécution des processus) : on trouvera donc des différences même entre les différents systèmes Unix (Linux, MacOS, BSD, etc.). Les conventions présentées dans ce cours sont celles du système Linux, qui est la version la plus courante d'Unix. On peut les adapter sans trop de difficultés pour faire fonctionner les exemples du cours sous d'autres systèmes (notamment MacOS), mais certains cas d'utilisation (peu utilisés en pratique) ne seront pas possibles.

Au dela de ces différences techniques, c'est justement un des but du cours de Logiciel de Base de comprendre que lorsqu'on écrit du code bas-niveau, on est souvent confronté à des problèmes spécifiques au système sur lequel on travaille, et qu'il est difficile (voire impossible) d'écrire du code bas-niveau portable d'un système à l'autre.

Structure de la pile d'exécution d'un processus

Introduction

On a vu dans une séance précédente qu'un processus a une structure ressemblant au schéma suivant :

zone text
(code du programme)
zone data
(données statiques)
tas (heap)
(données dynamiques)
pile (stack)
(contexte d'exécution)

On a détaillé le contenu des zones text et data qui contiennent respectivement le code et les données statiques. Le tas est la zone dans laquelle les fonctions d'allocation dynamique de mémoire prennent l'espace mémoire à réserver : sa gestion interne est complexe et sera détaillée dans le cours de système de 2A. On va étudier en détail dans cette séance la structuration de la dernière zone : la pile d'exécution.

Définition d'un cadre de pile

La pile est la zone mémoire contenant le contexte d'exécution des fonctions du programme. A chaque fois que le programme commence l'exécution d'une fonction, on doit mettre en place un cadre de pile (stack frame en anglais) qui contiendra notamment les variables locales de la fonction, les paramètres passés à la fonction, etc. Un cadre de pile a la structure suivante :

(registres)
variables locales
%ebp précédent
adresse de retour
paramètres

Dans ce schéma, les adresses sont croissantes vers le bas mais les valeurs sont empilées en haut car il s'agit d'une pile au sens algorithmique du terme. Les différentes zones sont détaillées ci-dessous :

  • les paramètres sont ceux passés à la fonction en cours d'exécution ;
  • l'adresse de retour est l'adresse de l'instruction suivant l'appel de la fonction en cours d'exécution dans la fonction appelante (i.e. c'est là qu'on revient quand on exécute return à la fin de la fonction) ;
  • le « %ebp précédent » est la sauvegarde du pointeur de base de la fonction appelante (on détaillera son rôle plus bas) ;
  • les variables locales de la fonction en cours d'exécution sont localisées dans son cadre de pile, à des adresses fixes par rapport à %ebp ;
  • on peut éventuellement réserver de la place dans le cadre de pile pour sauvegarder des registres si besoin.

Les pointeurs de pile

Le Pentium comprend 2 registres dont le rôle est lié à la pile d'exécution : %esp et %ebp.

%esp est le pointeur de pile : il contient en permanence l'adresse de la dernière case occupée dans la pile d'exécution. On ne le manipule pas directement en général pour éviter de risquer de déséquilibrer la pile.

%ebp est le pointeur de base : il contient l'adresse de la base du contexte d'exécution de la fonction en cours d'exécution. Dans notre cas, il pointera en permanence sur la case dans laquelle on a sauvegardé le %ebp précédent. On se sert de %ebp pour accéder aux variables locales et aux paramètres de la fonction en cours d'exécution, via un adressage indirect avec déplacement (e.g. -4(%ebp), 8(%ebp), etc.).

Appels de fonctions

L'instruction call permet d'appeler une fonction : on l'utilise en précisant l'étiquette correspondant au début de la fonction à appeler, par exemple call pgcd. Cette instruction a le même comportement qu'un branchement inconditionnel (jmp) mais en plus, elle empile automatiquement l'adresse de retour dans la pile d'exécution. L'adresse de retour est simplement l'adresse de l'instruction suivant le call dans la fonction appelante.

L'instruction réciproque s'appelle ret : elle dépile l'adresse de retour et revient donc à l'instruction suivant le call. C'est l'équivalent de l'instruction return qu'on a déjà vu en Ada et en C.

Comme on l'a déjà vu dans les exemples des séances précédentes, on renvoie par convention le résultat de la fonction dans le registre %eax. On ne traitera pas dans le cadre de ce cours le cas particulier des fonctions renvoyant une valeur de taille inférieure ou supérieure à 32 bits.

Mise en place du cadre de pile

Le cadre de pile d'une fonction est mis en place en deux temps :

  • dans la fonction appelante, qui copie les paramètres qu'elle va passer à la fonction appelée et empile l'adresse de retour en exécutant call ;
  • dans la fonction appelée, qui réserve la place nécessaire à son contexte d'exécution.

Lorsqu'on écrit le code d'une fonction, on commence par l'instruction enter qui a pour rôle de réserver l'espace nécessaire au contexte d'exécution. Jusqu'à présent, on l'a toujours utilisée sous la forme enter $0, $0 mais le premier paramètre sera en général différent de zéro, et précise justement le nombre d'octets à réserver pour le contexte (le deuxième paramètre sera toujours 0 dans notre cas). L'instruction enter $N, $0 est en fait équivalente à la suite d'instructions suivante :

subl $4, %esp
movl %ebp, (%esp)
movl %esp, %ebp
subl $N, %esp

Comme %esp pointe par convention sur la dernière case occupée, on doit commencer par le décrémenter de 4 avant de pouvoir sauvegarder %ebp dans la pile : c'est la sauvegarde du %ebp précédent dans le schéma du cadre de pile ci-dessus. Ensuite, on fait pointer %ebp sur la case où on a sauvegardé son ancienne valeur, et on décrémente %esp de N octets : c'est cette opération qui réserve la place nécessaire au cadre de pile. On rappelle que la pile « descend » vers les adresses décroissantes, d'où le fait qu'on effectue des soustractions.

L'instruction réciproque de enter s'appelle leave. Elle s'utilise sans paramètre et a pour effet de détruire le cadre de pile mis en place par enter. Elle est équivalente à la séquence d'instructions :

movl %ebp, %esp
movl (%esp), %ebp
addl $4, %esp

Elle commence par faire pointer %esp sur la case contenant l'ancienne valeur de %ebp : c'est comme cela qu'on détruit le cadre de pile (la mémoire n'est bien sûr pas « vidée » et contient toujours les valeurs précédentes, mais ces valeurs ne doivent plus être utilisées par le programme). Ensuite, on restaure l'ancienne valeur de %ebp en le dépilant.

Exemple

Soit par exemple la fonction suivante :

int plus(void)
{
    int a = 5;
    int b = 4;
    return a + b;
}

En assembleur, on écrira :

plus:
    // on precisera toujours la position dans la pile de chaque variable
    //   (pour faciliter la relecture du code !)
    //     int a : ebp - 4
    //     int b : ebp - 8
    // on doit reserver de la place pour 2 variables locales
    // chaque variable prend 4 octets (int), donc 8 octets au total
    enter $8, $0
    // a = 5
    movl $5, -4(%ebp)
    // b = 4
    movl $4, -8(%ebp)
    // calcul de a + b
    movl -4(%ebp), %eax
    addl -8(%ebp), %eax
fin_plus:
    // la valeur a renvoyer est bien dans %eax a ce point
    leave
    ret

L'ordre dans lequel les variables locales sont placées dans la pile est arbitraire : il faut juste toujours garder la même convention. Dans notre cas on les placera simplement dans l'ordre de déclaration.

Dans l'exemple ci-dessus, la pile est donc dans l'état suivant lorsqu'on arrive sur l'étiquette fin_plus :

b = 4
a = 5
%ebp précédent
adresse de retour

Les cadres de pile s'empilent les uns au dessus des autres lors des appels de fonction. Par exemple, si la fonction plus ci-dessus est appelée par la fonction main comme suit :

int main(void)
{
    int x = plus();
    return 0;
}

On écrira en assembleur :

main:
    // int x : ebp - 4
    // il y a une seule variable locale de type int
    enter $4, $0
    // appel a plus
    call plus
    // x = plus()
    movl %eax, -4(%ebp)
    leave
    // return 0
    movl $0, %eax
    ret

La pile sera dans l'état suivant lorsqu'on arrivera à l'étiquette fin_plus :

b = 4
a = 5
%ebp de main
adresse de retour à main
x = ?
%ebp du système
adresse de retour au système

La variable locale x n'a pas de valeur à ce moment-là car elle sera affectée dans main en revenant de l'appel à plus.

Passage de paramètres

Une fonction qui souhaite en appeler une autre en lui passant des paramètres doit les copier sur la pile avant d'exécuter l'instruction call.

Par exemple, si on modifie la fonction plus de l'exemple précédent pour qu'elle appelle une autre fonction affichant les valeurs à ajouter :

int plus(void)
{
    int a = 5;
    int b = 4;
    affichage(a, b);
    return a + b;
}

On va copier les valeurs de a et b dans la pile juste avant l'appel à la fonction affichage (il s'agit bien d'une copie, comme pour le passage de paramètres par copie du C).

On utilise pour ça l'instruction push, qui a pour effet d'empiler une valeur, c'est à dire :

  • de déplacer le pointeur de pile %esp qui pointe sur la dernière case occupée ;
  • de copier la valeur dans la case mémoire pointée maintenant par %esp.

Par exemple, pushl %eax est équivalent à :

subl $4, %esp
movl %eax, (%esp)

Le Pentium permet d'empiler des valeurs sur 16 ou 32 bits (pas des valeurs sur 8 bits). En pratique, on n'utilisera push qu'avec des valeurs sur 32 bits, pour respecter des contraintes d'alignement mémoire. On pourra donc écrire par exemple :

pushl %eax // empile le contenu du registre %eax
pushl $5 // empile la constante 5
pushl -4(%ebp) // empile le contenu d'une variable locale

On voit qu'il est possible d'empiler directement le contenu d'une variable (locale dans l'exemple, mais elle pourrait aussi être globale). L'instruction push est donc capable de faire des copies de mémoire à mémoire.

L'instruction réciproque s'appelle pop et elle permet de dépiler la valeur en sommet de pile. Par exemple, popl %eax est équivalent à :

movl (%esp), %eax
addl $4, %esp

Il est donc facile de copier sur la pile les paramètres à passer à une fonction en utilisant l'instruction push. Il faut cependant faire attention à l'ordre dans lequel on les copie : il faut respecter le même ordre dans la fonction appelante (qui copie les paramètres) et la fonction appelée (qui va les lire sur la pile). On utilisera la convention adoptée en C, où on copie les paramètres dans l'ordre des adresses croissantes : dans l'exemple de la fonction plus, on copiera donc a à l'adresse %ebp - 16 et b à l'adresse %ebp - 12.

Le code assembleur correspondant à la fonction plus sera donc :

plus:
    // int a : %ebp - 4
    // int b : %ebp - 8
    // 2 variables locales de 4 octets chacunes (int)
    enter $8, $0
    // a = 5
    movl $5, -4(%ebp)
    // b = 4
    movl $4, -8(%ebp)
    // affichage(a, b)
    pushl -8(%ebp)
    pushl -4(%ebp)
    call affichage
    addl $8, %esp
    // return a + b
    movl -4(%ebp), %eax
    addl -8(%ebp), %eax
    leave
    ret

Lorsqu'on entre dans la fonction affichage (juste après avoir effectué le call), la pile d'exécution sera donc dans l'état suivant :

%ebp de plus
adresse de retour à plus
param a = 5
param b = 4
b = 4
a = 5
%ebp de main
adresse de retour à main

On note l'instruction addl $8, %esp juste après le call affiche. En effet, il est important de maintenir l'équilibre de la pile en évitant d'y laisser des valeurs inutiles (dans le cas d'une fonction récursive par exemple, on pourrait rapidement arriver à saturer l'espace mémoire réservé pour la pile d'exécution). On doit donc dépiler les paramètres une fois l'appel à la fonction réalisé. On pourrait utiliser pop mais en pratique, on n'a pas besoin de récupérer les valeurs empilées. On peut donc simplement déplacer le pointeur de pile pour le remettre à sa position avant les push : dans le cas de cet exemple, on a empilé deux paramètres de 4 octets chacun, donc il suffit d'ajouter 8 à %esp.

Récupération de paramètres

Réciproquement, dans la fonction appelée, on va accéder aux paramètres passés par la fonction appelante dans la pile. Ces paramètres sont situés tout en bas du contexte d'exécution, « sous » la position actuelle de %ebp. Comme la pile se remplit vers les adresses décroissantes, cela signifie qu'on va récupérer les paramètres à l'aide d'un déplacement positif par rapport à %ebp.

Entre la position actuelle de %ebp et le premier paramètre, il ne faut pas oublier que l'instruction call a placé l'adresse de retour à la fonction appelante. Le premier paramètre est donc situé à l'adresse %ebp + 8 (et pas + 4).

Par exemple, si on modifie la fonction plus de façon à ce qu'elle fasse la somme de ses paramètres :

int plus(int a, int b)
{
    return a + b;
}

Le code assembleur correspondant sera :

plus:
    // pas de variable locale
    enter $0, $0
    // calcul de a + b
    // on recupere la valeur de a dans %eax
    movl 8(%ebp), %eax
    // on ajoute la valeur de b a %eax
    addl 12(%ebp), %eax
    // la valeur a renvoyer est bien dans %eax a ce point
fin_plus:
    leave
    ret

Interaction avec le langage C

On écrit très rarement des programmes entièrement en assembleur : en général, un programme sera composé de fonctions C et assembleur s'appelant les unes les autres. Il est donc important de respecter les mêmes conventions que le compilateur C lorsqu'on écrit du code assembleur devant interagir avec du code C.

Gestion des registres

Le compilateur GCC classe les registres généraux du processeur dans 2 catégories :

  • les registres scratch sont des registres « de calcul » qui peuvent être utilisés librement dans les fonctions en assembleur ;
  • les registres non-scratch sont des registres « précieux » dans lesquels le compilateur peut stocker des valeurs importantes.

Sur Pentium :

  • les registres scratch sont %eax, %edx et %ecx ;
  • les registres non-scratch sont %ebx, %esi et %edi.

Il s'agit d'une convention arbitraire : on doit cependant la prendre en compte lorsqu'on veut interagir avec du code généré par GCC.

Appel d'une fonction assembleur depuis une fonction C

Sans le savoir, on a toujours écrit du code assembleur appelé depuis une fonction C. En effet, lors de la création du binaire final, le compilateur a lié le programme avec un module (appelé crt0) dont le rôle est de préparer l'exécution du programme et qui se termine par un appel à la fonction main.

Pour appeler une fonction écrite en assembleur depuis du code écrit en C, on doit :

  • respecter la convention de pile présentée dans la première partie, notamment en ce qui concerne la gestion des paramètres ;
  • respecter la convention de gestion des registres, et plus précisément :
    • la fonction en assembleur ne doit pas modifier le contenu des registres non-scratch avant de les avoir sauvegardé : en effet, la fonction C appelante a pu laisser des valeurs importantes dans ces registres, et s'attend à les retrouver au retour de la fonction assembleur ;
    • la fonction en assembleur peut utiliser sans restriction les registres scratch.
  • respecter la convention de nommage des fonctions, qui dépend du système utilisé :
    • sous Linux les fonctions en assembleur sont nommées de la même façon que les fonctions en C ;
    • sous MacOS les fonctions en assembleur sont préfixées par un blanc-souligné (underscore, le caractère _ ).
  • rendre visible le prototype de la fonction assembleur là où elle est appelée dans le programme en C et rendre public (avec la directive .globl) le point d'entrée de la fonction assembleur.

Par exemple, si on écrit une fonction main en C qui appelle la fonction plus renvoyant la somme de ces paramètres, on écrira en C :

#include <stdio.h>

// prototype de la fonction ecrite en assembleur
int plus(int a, int b);

int main(void)
{
    int a = 5;
    int b = 4;
    int x = plus(a, b);
    printf("La somme vaut %d\n", x);
    return 0;
}

et en assembleur, on pourrait écrire :

    .globl plus
    .globl _plus
plus:
_plus:
    // pas de variable locale
    enter $0, $0
    // sauvegarde du registre non-scratch %edi
    pushl %edi
    // calcul de a + b
    // on recupere la valeur de a dans %edi
    movl 8(%ebp), %edi
    // on ajoute la valeur de b a %edi
    addl 12(%ebp), %edi
    // on doit renvoyer la somme dans %eax
    movl %edi, %eax
    // restauration du registre %edi
    popl %edi
    leave
    ret

Dans ce code, on utilise le registre non-scratch %edi pour faire le calcul : il s'agit d'un exemple purement scolaire pour illustrer la sauvegarde d'un registre non-scratch car en pratique on aurait pu utiliser n'importe-quel registre scratch.

On note qu'on utilise deux étiquettes : plus et _plus, ce qui permet de rendre le code compatible aussi bien sous Linux que MacOS (mettre plusieurs étiquettes désignant le même point ne pose évidemment aucun problème).

Appel d'une fonction C depuis une fonction assembleur

On peut avoir besoin d'appeler une fonction C depuis du code assembleur (cas beaucoup moins fréquent que la réciproque en pratique). Ce cas est délicat car il impose de respecter des conventions très différentes d'un système à l'autre. On a choisi ici de respecter la convention utilisé sous Linux, et de l'adapter autant que possible aux contraintes des autres systèmes (comme MacOS par exemple). La convention choisie n'est pas parfaite (certains cas d'utilisation ne seront pas possibles) mais présente l'avantage de la simplicité et est suffisante pour les exemples vus dans le cadre de ce cours.

Pour appeler une fonction écrite en C depuis de l'assembleur, on doit donc :

  • respecter la convention de pile présentée dans la première partie, notamment en ce qui concerne la gestion des paramètres ;
  • respecter la convention de gestion des registres, et plus précisément :
    • la fonction en assembleur ne doit pas laisser de valeurs importantes dans les registres scratch sans les sauvegarder avant d'appeler la fonction C : en effet, l'appel à la fonction C pourrait parfaitement détruire le contenu de ces registres, car GCC considère qu'il peut s'en servir comme bon lui semble ;
    • la fonction en assembleur peut par contre laisser des valeurs importantes dans les registres non-scratch car on est sur qu'ils ne seront pas modifiés par l'appel à la fonction C.
  • respecter la convention de nommage des fonctions, qui dépend du système utilisé :
    • sous Linux on peut appeler directement la fonction C fct grâce à call fct ;
    • sous MacOS on doit préfixer le nom de la fonction par un blanc-souligné : call _fct.

Cette convention marche sous Linux. Sous MacOS, on doit de plus respecter deux contraintes supplémentaires :

  • ajouter l'option -mstackrealign lors de la compilation du programme (cette option n'existe pas sous Linux) ;
  • s'interdire d'appeler directement une fonction de la bibliothèque C depuis le code assembleur (e.g. call _printf) : cette restriction n'est en pratique pas très gênante car il est possible d'encapsuler les appels à la bibliothèque C dans des fonctions écrites en C, qui seront elles-mêmes appelées depuis l'assembleur.

Par exemple, si on écrit une version de la fonction plus qui effectue un affichage de la somme effectuée et qu'on suppose la fonction affiche écrite en C :

#include <stdio.h>

void affiche(int z)
{
    printf("La somme vaut %d\n", z);
}

int plus(void)
{
    int a = 5;
    int b = 4;
    affiche(a + b);
    return a + b;
}

On pourrait écrire plus en assembleur comme suit :

_plus:
plus:
    // int a : %ebp - 4
    // int b : %ebp - 8
    // 2 variables locales de 4 octets chacunes (int)
    enter $8, $0
    // a = 5
    movl $5, -4(%ebp)
    // b = 4
    movl $4, -8(%ebp)
    // calcule de a + b
    movl -4(%ebp), %eax
    addl -8(%ebp), %eax
    // sauvegarde de %eax
    pushl %eax
    // affiche(a + b)
    pushl %eax
    // sous Linux
    call affiche
    // OU sous MacOS : call _affiche
    addl $4, %esp
    // restauration de %eax = a + b
    popl %eax
    // return a + b
    leave
    ret

On a choisi de laisser la somme a + b dans %eax pour illustrer la sauvegarde d'un registre scratch : on aurait parfaitement pu écrire le code d'une façon ne nécessitant pas cette sauvegarde.

On voit que dans cet exemple particulier, on copie deux fois %eax dans la pile : une fois pour le sauvegarder, et une fois pour passer son contenu en paramètre à la fonction affiche. On pourrait être tenté « d'optimiser » le code en ne le copiant qu'une seule fois et en supprimant le addl juste après le call : de façon générale, il faut se retenir d'effectuer ce genre d'optimisations ad-hoc (à moins qu'on vous le demande spécifiquement) car :

  1. le gain en temps d'exécution est souvent marginal (voire parfois négatif si on s'y prend mal) ;
  2. un code écrit de façon systématique a plus de chance d'être correct qu'un code « bidouillé » !

On doit bien respecter la convention de nommage du système utilisé lors de l'appel à la fonction écrite en C (e.g. call affiche sous Linux ou call _affiche sous MacOS).

Exercices

PGCD

Ecrire le code assembleur correspondant à la fonction PGCD ci-dessous :

unsigned pgcd(unsigned a, unsigned b)
{
    while (a != b) {
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    return a;
}

Multiplication

Ecrire en assembleur la fonction de multiplication simple ci-dessous :

unsigned mult(unsigned x, unsigned y);
{
    unsigned res = 0;
    while (y != 0) {
        res = res + x;
        y--;
    }
    return res;
}

Suite de Fibonacci

Ecrire en assembleur la fonction récursive ci-dessous :

unsigned fibo(unsigned n);
{
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibo(n - 1) + fibo(n - 2);
    }
}