3MMCEP TP Structures : Différence entre versions

De Ensiwiki
Aller à : navigation, rechercher
 
(13 révisions intermédiaires par 2 utilisateurs non affichées)
Ligne 1 : Ligne 1 :
 +
{{Maintenance uniquement par enseignants}}
 +
 
{{1A}} {{Informatique}}
 
{{1A}} {{Informatique}}
  
 
[[Catégorie:Première Année]]
 
[[Catégorie:Première Année]]
 
[[Catégorie:Informatique]]
 
[[Catégorie:Informatique]]
 +
 +
{{PageDeBase|3MMCEP}}
  
 
== Introduction ==
 
== Introduction ==
Ligne 8 : Ligne 12 :
 
Le but de cette séance est de pratiquer la manipulation de structures et de pointeurs en assembleur : il est essentiel d'être à l'aise sur ses notions pour l'examen de TP final.
 
Le but de cette séance est de pratiquer la manipulation de structures et de pointeurs en assembleur : il est essentiel d'être à l'aise sur ses notions pour l'examen de TP final.
  
Commencez par récupérer les sources utiles pour cette séance.
+
Commencez par récupérer les [[Media:3MMCEP_TP_Structures_src.zip|sources utiles pour cette séance]].
  
 
== Rappel préliminaire ==
 
== Rappel préliminaire ==
Ligne 60 : Ligne 64 :
 
* <tt>ptr = 0xBADC0FFEE0DDF00D</tt>
 
* <tt>ptr = 0xBADC0FFEE0DDF00D</tt>
  
La fonction <tt>affichage</tt> prend en paramètre la structure <tt>s<tt>. Cette fonction est définie dans le fichier <tt>fct_struct.s</tt> par :
+
La fonction <tt>affichage</tt> prend en paramètre la structure <tt>s</tt>. Cette fonction est définie dans le fichier <tt>fct_struct.s</tt> par :
 
<pre>
 
<pre>
 
     .globl affichage
 
     .globl affichage
Ligne 76 : Ligne 80 :
  
 
En pratique, ce découpage est déjà fait par le compilateur C : l'ABI impose en effet que les champs sur 64 bits d'une structure sont passés en paramètres dans les registres habituels (<tt>%rdi</tt>, <tt>%rsi</tt>, <tt>%rdx</tt>, etc.). Le champ <tt>entier</tt> est donc passé dans <tt>%rdi</tt> et le champ <tt>ptr</tt> est passé dans <tt>%rsi</tt>.
 
En pratique, ce découpage est déjà fait par le compilateur C : l'ABI impose en effet que les champs sur 64 bits d'une structure sont passés en paramètres dans les registres habituels (<tt>%rdi</tt>, <tt>%rsi</tt>, <tt>%rdx</tt>, etc.). Le champ <tt>entier</tt> est donc passé dans <tt>%rdi</tt> et le champ <tt>ptr</tt> est passé dans <tt>%rsi</tt>.
 +
 +
On a conseillé à la séance précédente de sauvegarder systématiquement les paramètres lorsque la fonction qu'on écrit appelle elle-même une autre fonction : ici, c'est visiblement inutile de sauvegarder <tt>%rdi</tt> et <tt>%rsi</tt> avant d'appeler <tt>affiche</tt>, car la fonction <tt>affichage</tt> se termine tout de suite après l'appel : on n'aura plus besoin des valeurs initiale des paramètres (mais un compilateur C non-optimisant les sauvegarderait tout de même).
  
 
L'appel à <tt>affiche</tt> est donc immédiat, vu qu'on a déjà les bons champs dans les bons registres.
 
L'appel à <tt>affiche</tt> est donc immédiat, vu qu'on a déjà les bons champs dans les bons registres.
Ligne 105 : Ligne 111 :
 
ce qui s'écrit simplement <tt>movq %rdi, (%rdx)</tt>. On rappelle que le premier champ d'une structure est situé à la même adresse que la structure elle-même.
 
ce qui s'écrit simplement <tt>movq %rdi, (%rdx)</tt>. On rappelle que le premier champ d'une structure est situé à la même adresse que la structure elle-même.
  
Pour le champs <tt>ptr</tt>, le principe est le même sauf que le champ <ptr> ne se situe pas dans la case pointée par <tt>ps</tt> mais 8 octets plus loin (c'est le deuxième champ de la structure, et le premier champ prend 8 octets). On écrira donc <tt>movq %rsi, 8(%rdx)</tt> puisque le deuxième paramètre (<tt>p</tt>) est dans <tt>%rsi</tt>.
+
Pour le champs <tt>ptr</tt>, le principe est le même sauf que le champ <tt>ptr</tt> ne se situe pas dans la case pointée par <tt>ps</tt> mais 8 octets plus loin (c'est le deuxième champ de la structure, et le premier champ prend 8 octets). On écrira donc <tt>movq %rsi, 8(%rdx)</tt> puisque le deuxième paramètre (<tt>p</tt>) est dans <tt>%rsi</tt>.
  
<!--
+
== Exercices ==
  
Ecrivez en assembleur dans un fichier <tt>struct.s</tt> les deux fonctions dont on donne le code C ci-dessous :
+
=== Utilisation de <tt>valgrind</tt> ===
<pre>
+
void affichage(struct structure_t s)
+
{
+
    affiche(s.entier, s.ptr);
+
}
+
  
void modification(int entier, char *ptr, struct structure_t *s)
+
L'outil [http://valgrind.org/ Valgrind] est très utile pour détecter les erreurs d'accès ou les fuites mémoire dans un programme (écrit en C, assembleur, Ada, etc.).
{
+
    s->entier = entier;
+
    s->ptr = ptr;
+
}
+
</pre>
+
  
Ces fonctions s'écrivent en quelques lignes d'assembleur chacune, mais il est important de bien comprendre les accès mémoires, notamment les calculs à faire pour accéder aux champs de la structure.
+
Pour vous entrainer à son utilisation, on fourni un fichier <tt>fct_progbug.s</tt> qui contient deux fonctions volontairement fausses. Pour rendre les choses plus amusantes, elles ne sont pas commentées. Le fichier <tt>progbug.c</tt> contient un programme principal qui ne fait qu'appeler ces deux fonctions. Pour commencer, on a commenté la fonction <tt>bug2</tt> afin de traquer chaque problème un par un.
  
On peut compiler le programme grâce à la commande <tt>gcc -Wall -Wextra -m32 -g -std=c99 struct.c struct.s -o struct</tt>.
+
Commencez par compiler en tapant <tt>make progbug</tt> puis exécuter le programme : <tt>./progbug</tt> : aucun message d'erreur n'apparait. Vous pouvez si vous le souhaitez exécuter pas à pas le programme dans GDB, ce qui ne devrait pas beaucoup vous aider non plus.
  
Pour mettre au point votre code, vous aurez certainement besoin de GDB et de Valgrind, l'outil de validation des accès mémoire, que vous pouvez exécuter en tapant <tt>valgrind --leak-check=full ./struct</tt>.
+
Executez maintenant la commande <tt>valgrind --leak-check=full ./progbug</tt> : le message affiché doit vous permettre de comprendre l'origine du problème (oui, c'est en anglais !).
  
'''Attention''' : certaines versions récentes de Valgrind ne supportent pas l'instruction <tt>enter</tt> que l'on utilise au début des fonctions écrites en assembleur. Si vous obtenez une erreur du genre <tt>vex x86->IR: unhandled instruction bytes: 0xC8</tt> à l'exécution, vous pouvez remplacer la ligne <tt>enter $N, $0</tt> par les trois lignes suivantes (où N est bien sûr à remplacer par la taille de la zone contenant les variables locales dans votre programme) :
+
Ouvrez <tt>progbug.c</tt>, commentez l'appel à <tt>bug1</tt> et décommentez l'appel à <tt>bug2</tt> et répétez le processus pour comprendre le deuxième problème.
<pre>
+
pushl %ebp
+
movl %esp, %ebp
+
subl $N, %esp
+
</pre>
+
  
== Manipulation de listes chaînees ==
+
=== Manipulation de listes chaînees ===
  
Dans cet exercice, on va manipuler des listes chainées de cellules définies par :
+
Dans cet exercice, on va manipuler des listes chainées de cellules définies dans le fichier <tt>liste.c</tt> par :
 
<pre>
 
<pre>
 
struct cellule_t {
 
struct cellule_t {
     int val;
+
     int64_t val;
 
     struct cellule_t *suiv;
 
     struct cellule_t *suiv;
 
};
 
};
 
</pre>
 
</pre>
  
Copiez-collez dans un fichier <tt>liste.c</tt> le programme principal ci-dessous qui vous permettra de tester votre code :
+
Ce fichier contient un programme de test qui génère un tableau de 10 entiers aléatoires puis le convertit en liste chaînée et appelle les fonctions à implanter en assembleur.
<pre>
+
#include <time.h>
+
#include <stdio.h>
+
#include <assert.h>
+
#include <stdlib.h>
+
  
struct cellule_t {
+
La première fonction à implanter est <tt>inverse</tt> qui prend en paramètre un pointeur sur une liste chaînée (donc un pointeur sur un pointeur sur une cellule), inverse la liste pointée, et met à jour le pointeur passé en paramètre pour qu'il pointe sur la liste inversée.
    int val;
+
    struct cellule_t *suiv;
+
};
+
  
// cree une liste chainee a partir d'un tableau d'entiers termine par -1
+
On vous demande comme toujours de traduire littéralement le code C donné en commentaire et de respecter les conventions de gestion de la pile et des registres.
// les elements sont inseres dans l'ordre inverse par rapport au tableau initial
+
struct cellule_t *cree_liste(int tab[])
+
{
+
    struct cellule_t *liste = NULL;
+
    for (int i = 0; tab[i] != -1; i++) {
+
        struct cellule_t *cell = malloc(sizeof(struct cellule_t));
+
        assert(cell != NULL);
+
        cell->val = tab[i];
+
        cell->suiv = liste;
+
        liste = cell;
+
    }
+
    return liste;
+
}
+
  
// affiche une liste chainee d'entiers
+
Ensuite, vous devez implanter la fonction <tt>decoupe</tt> qui prend en paramètre une liste chaînée (donc un pointeur sur une cellule), ainsi que deux pointeurs sur listes : ces deux paramètres correspondent aux deux listes résultat qu'on doit obtenir après le découpage (le critère de découpage choisi ici étant la parité de la valeur d'une cellule).
void affiche_liste(struct cellule_t *liste)
+
{
+
    for (; liste != NULL; liste = liste->suiv) {
+
        printf("%d -> ", liste->val);
+
    }
+
    printf("FIN\n");
+
}
+
  
// detruit une liste chainee d'entiers
+
La fonction <tt>decoupe</tt> a besoin de deux variables locales <tt>fictif1</tt> et <tt>fictif2</tt> qui sont de type cellule : c'est à dire que chacune de ces variables occupe 16 octets et contient deux champs, la valeur et le pointeur vers la cellule suivante (comme il s'agit d'éléments fictifs placés en tête de liste pour faciliter les insertions, on ne se servira pas de leurs champs <tt>val</tt>, mais on est obligé de l'allouer quand même si on traduit littérallement le type <tt>cellule_t</tt>).
void detruit_liste(struct cellule_t *liste)
+
{
+
    while (liste != NULL) {
+
        struct cellule_t *suiv = liste->suiv;
+
        free(liste);
+
        liste = suiv;
+
    }
+
}
+
  
void inverse(struct cellule_t **l);
+
On rappelle que <tt>lea</tt> est l'instruction permettant de calculer l'adresse d'une variable.
 
+
struct cellule_t *decoupe(struct cellule_t *l, struct cellule_t **l1, struct cellule_t **l2);
+
 
+
// une fonction de test basique
+
void test(int tableau[])
+
{
+
    struct cellule_t *liste, *l1, *l2;
+
    printf("Tableau initial : ");
+
    for (int i = 0; tableau[i] != -1; i++) {
+
        printf("%i ", tableau[i]);
+
    }
+
    printf("\n");
+
    liste = cree_liste(tableau);
+
    printf("Liste initiale : ");
+
    affiche_liste(liste);
+
    printf("Liste inversee : ");
+
    inverse(&liste);
+
    affiche_liste(liste);
+
    liste = decoupe(liste, &l1, &l2);
+
    printf("Liste initiale apres le decoupage : ");
+
    affiche_liste(liste);
+
    printf("Liste des elements impairs : ");
+
    affiche_liste(l1);
+
    printf("Liste des elements pairs : ");
+
    affiche_liste(l2);
+
    detruit_liste(liste);
+
    detruit_liste(l1);
+
    detruit_liste(l2);
+
}
+
 
+
int main(void)
+
{
+
    const int taille_tab = 11;
+
    int tableau[taille_tab];
+
    srand(time(NULL));
+
 
+
    printf("** Test d'un tableau quelconque **\n");
+
    for (int i = 0; i < taille_tab - 1; i++) {
+
        tableau[i] = rand() % 10;
+
    }
+
    tableau[taille_tab - 1] = -1;
+
    test(tableau);
+
 
+
    printf("\n** Test d'un tableau avec seulement des elements pairs **\n");
+
    for (int i = 0; i < taille_tab - 1; i++) {
+
        tableau[i] = (rand() % 10) & ~1;
+
    }
+
    tableau[taille_tab - 1] = -1;
+
    test(tableau);
+
 
+
    printf("\n** Test d'un tableau avec seulement des elements impairs **\n");
+
    for (int i = 0; i < taille_tab - 1; i++) {
+
        tableau[i] = (rand() % 10) | 1;
+
    }
+
    tableau[taille_tab - 1] = -1;
+
    test(tableau);
+
 
+
    printf("\n** Test d'un tableau vide **\n");
+
    tableau[0] = -1;
+
    test(tableau);
+
 
+
    return 0;
+
}
+
</pre>
+
 
+
Commencez par écrire en assembleur dans un fichier <tt>liste.s</tt> la fonction suivante :
+
<pre>
+
void inverse(struct cellule_t **l)
+
+
  struct cellule_t *res, *suiv;
+
  res = NULL;
+
  while (*l != NULL) {
+
      suiv = (*l)->suiv;
+
      (*l)->suiv = res;
+
      res = *l;
+
      *l = suiv;
+
  } 
+
  *l = res;
+
}
+
</pre>
+
 
+
Cette fonction prend en paramètre l'adresse d'une liste chaînée (''i.e.'' un pointeur sur un pointeur sur la cellule de tête de la liste) et inverse son contenu.
+
 
+
On demande ensuite de traduire en assembleur dans le fichier <tt>liste.s</tt> la fonction :
+
 
+
<pre>
+
struct cellule_t *decoupe(struct cellule_t *l, struct cellule_t **l1, struct cellule_t **l2)
+
{
+
    struct cellule_t sent1, sent2;
+
    *l1 = &sent1;
+
    *l2 = &sent2;
+
    while (l != NULL) {
+
        if (l->val % 2 == 1) {
+
            (*l1)->suiv = l;
+
            *l1 = l;
+
        } else {
+
            (*l2)->suiv = l;
+
            *l2 = l;
+
        }
+
        l = l->suiv;
+
    }
+
    (*l1)->suiv = NULL;
+
    (*l2)->suiv = NULL;
+
    *l1 = sent1.suiv;
+
    *l2 = sent2.suiv;
+
    return l;
+
}
+
</pre>
+
 
+
Cette fonction prend en entrée une liste chainée <tt>l</tt> et produit en sortie deux listes <tt>l1</tt> et <tt>l2</tt> composées respectivement des élèments impairs et pairs de <tt>l</tt>.
+
 
+
Utilisez là aussi Valgrind pour mettre au point votre programme.
+
 
+
Pour vous entrainer à manipuler les pointeurs, vous pouvez écrire en assembleur les fonctions <tt>cree_liste</tt>, <tt>affiche_liste</tt> et <tt>detruit_liste</tt> dont on donne le code C ci-dessus (note : <tt>assert</tt> étant une macro, vous ne pouvez pas l'appeler depuis l'assembleur : ignorez donc la liste concernée).
+
 
+
== Tri du nain de jardin ==
+
 
+
Si vous n'avez pas fini le tri du nain de jardin présenté à la [[CEP_CTD_Fonctions#Passage_de_tableaux_en_param.C3.A8tre|séance précédente]], vous devez le finir maintenant !
+
 
+
== Si vous avez fini en avance ==
+
 
+
Reprenez le programme de test du tri du nain de jardin ci-dessus, mais remplacer ce tri par un tri par insertion, que vous implanterez en assembleur en traduisant la fonction C ci-dessous :
+
<pre>
+
for (unsigned i = 1; i < taille; i++) {
+
    int v = tab[i];
+
    unsigned j = i;
+
    while ((j > 0) && (tab[j-1] > v)) {
+
        tab[j] = tab[j-1];
+
        j--;
+
    }
+
    tab[j] = v;
+
}
+
</pre>
+
-->
+

Version actuelle en date du 11 avril 2017 à 09:26

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 
Fleche haut.png

Introduction

Le but de cette séance est de pratiquer la manipulation de structures et de pointeurs en assembleur : il est essentiel d'être à l'aise sur ses notions pour l'examen de TP final.

Commencez par récupérer les sources utiles pour cette séance.

Rappel préliminaire

En C, les structures de données (déclarées avec le mot-clé struct) sont stockées en mémoire selon des règles définies dans la spécification du langage et sur lesquelles on doit s'appuyer pour accéder aux différents champs en assembleur.

Soit par exemple la structure suivante :

struct structure_t {
    int64_t entier;
    char *ptr;
};

En mémoire, si on suppose que la structure est placée à l'adresse A, on aura :

  • le champ entier également à l'adresse A ;
  • le champ ptr à l'adresse A + 8, puisque ce champ est le deuxième de la structure, et que la taille du premier est 8 octets.

La spécification du langage C impose donc que les champs d'une structure soit stockés en mémoire dans le même ordre que leur déclaration.

Exemple détaillé

Dans le fichier struct.c, on trouve le programme suivant :

struct structure_t {
    int64_t entier;
    char *ptr;
};

void affiche(uint64_t entier, char *ptr)
{
    printf("entier = %" PRId64 ", ptr = 0x%" PRIX64 "\n", entier, (uint64_t)ptr);
}

void affichage(struct structure_t);

void modification(uint64_t, char*, struct structure_t*);

int main(void)
{
    struct structure_t s = {-1, (char*)0xBADC0FFEE0DDF00D};
    affichage(s);
    modification(5, (char*)0xDEADC0DED15EA5E, &s);
    affichage(s);
    return 0;
}

Ce programme défini le type structure_t comme plus haut, puis affecte les champs d'une variable s de ce type avec les valeurs initiales :

  • entier = -1
  • ptr = 0xBADC0FFEE0DDF00D

La fonction affichage prend en paramètre la structure s. Cette fonction est définie dans le fichier fct_struct.s par :

    .globl affichage
    // void affichage(struct structure_t s)
    // s : %rdi:%rsi
affichage:
    enter $0, $0
    // affiche(s.entier, s.ptr);
    call affiche
    leave
    ret

En fait, cette fonction reçoit simplement la structure en paramètre, puis appelle une autre fonction affiche (définie dans struct.c) pour réaliser l'affichage. La fonction affiche prend en paramètre un entier et un pointeur, ce qui veut dire que affichage ne sert qu'à « découper » la structure en deux champs.

En pratique, ce découpage est déjà fait par le compilateur C : l'ABI impose en effet que les champs sur 64 bits d'une structure sont passés en paramètres dans les registres habituels (%rdi, %rsi, %rdx, etc.). Le champ entier est donc passé dans %rdi et le champ ptr est passé dans %rsi.

On a conseillé à la séance précédente de sauvegarder systématiquement les paramètres lorsque la fonction qu'on écrit appelle elle-même une autre fonction : ici, c'est visiblement inutile de sauvegarder %rdi et %rsi avant d'appeler affiche, car la fonction affichage se termine tout de suite après l'appel : on n'aura plus besoin des valeurs initiale des paramètres (mais un compilateur C non-optimisant les sauvegarderait tout de même).

L'appel à affiche est donc immédiat, vu qu'on a déjà les bons champs dans les bons registres.

Ensuite, dans le programme principal, on appelle une fonction servant à modifier les champs de la structure : modification est définie dans le fichier fct_struct.s par :

    .globl modification
    // void modification(int64_t e, char *p, struct structure_t *ps)
    // e : %rdi
    // p : %rsi
    // ps : %rdx
modification:
    enter $0, $0
    // ps->entier = e;
    movq %rdi, (%rdx)
    // ps->ptr = p;
    movq %rsi, 8(%rdx)
    leave
    ret

Pour pouvoir modifier les champs de la structure s, on doit passer un pointeur vers cette structure à la fonction modification : c'est son troisième paramètre ps. Les deux premiers paramètres sont les nouvelles valeurs qu'on veut affecter aux champs de la structure.

En C, on peut écrire : ps->entier = e pour affecter la valeur de l'entier e au champ entier de la structure pointée par ps : cette notation est un raccourci équivalent à (*ps).entier = e.

Dans le code assembleur, on doit donc :

  • affecter la valeur du paramètre e qui est dans %rdi (premier paramètre),
  • dans la case pointée par le pointeur ps qui est dans %rdx (troisième paramètre),

ce qui s'écrit simplement movq %rdi, (%rdx). On rappelle que le premier champ d'une structure est situé à la même adresse que la structure elle-même.

Pour le champs ptr, le principe est le même sauf que le champ ptr ne se situe pas dans la case pointée par ps mais 8 octets plus loin (c'est le deuxième champ de la structure, et le premier champ prend 8 octets). On écrira donc movq %rsi, 8(%rdx) puisque le deuxième paramètre (p) est dans %rsi.

Exercices

Utilisation de valgrind

L'outil Valgrind est très utile pour détecter les erreurs d'accès ou les fuites mémoire dans un programme (écrit en C, assembleur, Ada, etc.).

Pour vous entrainer à son utilisation, on fourni un fichier fct_progbug.s qui contient deux fonctions volontairement fausses. Pour rendre les choses plus amusantes, elles ne sont pas commentées. Le fichier progbug.c contient un programme principal qui ne fait qu'appeler ces deux fonctions. Pour commencer, on a commenté la fonction bug2 afin de traquer chaque problème un par un.

Commencez par compiler en tapant make progbug puis exécuter le programme : ./progbug : aucun message d'erreur n'apparait. Vous pouvez si vous le souhaitez exécuter pas à pas le programme dans GDB, ce qui ne devrait pas beaucoup vous aider non plus.

Executez maintenant la commande valgrind --leak-check=full ./progbug : le message affiché doit vous permettre de comprendre l'origine du problème (oui, c'est en anglais !).

Ouvrez progbug.c, commentez l'appel à bug1 et décommentez l'appel à bug2 et répétez le processus pour comprendre le deuxième problème.

Manipulation de listes chaînees

Dans cet exercice, on va manipuler des listes chainées de cellules définies dans le fichier liste.c par :

struct cellule_t {
    int64_t val;
    struct cellule_t *suiv;
};

Ce fichier contient un programme de test qui génère un tableau de 10 entiers aléatoires puis le convertit en liste chaînée et appelle les fonctions à implanter en assembleur.

La première fonction à implanter est inverse qui prend en paramètre un pointeur sur une liste chaînée (donc un pointeur sur un pointeur sur une cellule), inverse la liste pointée, et met à jour le pointeur passé en paramètre pour qu'il pointe sur la liste inversée.

On vous demande comme toujours de traduire littéralement le code C donné en commentaire et de respecter les conventions de gestion de la pile et des registres.

Ensuite, vous devez implanter la fonction decoupe qui prend en paramètre une liste chaînée (donc un pointeur sur une cellule), ainsi que deux pointeurs sur listes : ces deux paramètres correspondent aux deux listes résultat qu'on doit obtenir après le découpage (le critère de découpage choisi ici étant la parité de la valeur d'une cellule).

La fonction decoupe a besoin de deux variables locales fictif1 et fictif2 qui sont de type cellule : c'est à dire que chacune de ces variables occupe 16 octets et contient deux champs, la valeur et le pointeur vers la cellule suivante (comme il s'agit d'éléments fictifs placés en tête de liste pour faciliter les insertions, on ne se servira pas de leurs champs val, mais on est obligé de l'allouer quand même si on traduit littérallement le type cellule_t).

On rappelle que lea est l'instruction permettant de calculer l'adresse d'une variable.