2014:01:13:TP:C:Memoires:01

Introduction

Ce TP sert d'introduction aux manipulations mémoires qui nous permettrons d'écrire notre version de malloc(3) (ou d'autres allocateurs spécifiques.)

Nous allons nous intéresser notamment à la fonction sbrk(2), aux symboles end(3), edata(3) et etext(3).

Où est ma mémoire ?

Notre objectif est d'observer la position de différents pointeurs, ainsi que d'autres éléments comme la pile ou le tas et les différents segments de notre programme.

Localisation des bases

Pour commencer, nous allons utiliser sbrk(2) pour récupérer la base de notre tas. La base est simple à récupérer, il s'agit de la limite (le break) de celui-ci avant d'y avoir toucher. La fonction sbrk(2) permet de déplacer le tas, mais elle renvoie également la position du break avant le déplacement, il suffit donc de déplacer le break de 0 octets et de récupérer cette adresse.

Pour pouvoir utiliser cette adresse tant que l'on veut, nous allons utiliser une variable static dans une fonction:

void *base() {
  static void  *brk_base;
  if (!brk_base)
    brk_base = sbrk(0);
  return brk_base;
}

Attention, pour être sûr que l'adresse obtenue soit correcte, il faut s'assurer que cette fonction soit appeler avant tout appelle à malloc(3) ou autre. Seulement, voila, toutes (ou presque) les fonctions de stdio.h utilisent le tas … Il faut donc appeler cette fonction le plus tôt possible.

Nous voulons maintenant une fonction qui affiche:

• la fin du segment de texte (voir etext(3))
• la fin du segment de donnée (voir edata(3))
• la fin du segment BSS (voir end(3))
• l'adresse initiale du tas (récupérer par notre fonction base().)

• Écrire la fonction void display_info(void) qui affiche les informations décrites précédemment, en respectant l'affichage suivant:

First address past:
    program text (etext)       0x8048886
    initialized data (edata)   0x804a020
    uninitialized data (end)   0x804a070
Initial break address:         0x9858000

Et maintenant regardons la pile …

• Écrire la fonction void *stack_base(void volatile *p) qui stocke et renvoie un pointeur. La spécification est simple: si p est différent de NULL alors, la fonction sauve p et renvoie sa nouvelle valeur. Sinon (p == NULL) la fonction renvoie la valeur sauvée.

Pour implémenter la fonction précédente, inspirez vous de la fonction base(). Nous l'utiliserons pour sauver (et après l'afficher) l'adresse de la première variable sur la pile de la fonction main. Ajouter cette adresse aux informations affichées par display_info().

Localiser un pointeur

Nous allons maintenant chercher à localiser différent pointeur vis à vis des adresses que nous avons identifier précédemment.

• Écrire la fonction void locate_ptr(void *p, char *msg) qui positionne le pointeur p par rapport aux différents points de repère (fin des ségments de texte, data et BSS, début du tas, première variable sur la pile … ) La chaîne msg sert uniquement à titre de documentation.

Voici une fonction main() utilisant nos fonctions:

char            global[64];
char            global_char = 'a';
 
int main() {
 
  char volatile mark_stack;
 
  stack_base(&mark_stack);
 
  display_info();
 
  char          local[64];
  char         *consttr = "a const string";
  char         *heap = malloc(64);
 
  locate_ptr(global,"global");
  locate_ptr(&global_char,"global_char");
  locate_ptr(consttr,"consttr");
  locate_ptr(local,"local");
  locate_ptr(heap,"heap");
 
  return 0;
}

La sortie obtenue, ressemble à ça:

First address past:
    program text (etext)       0x8048886
    initialized data (edata)   0x804a020
    uninitialized data (end)   0x804a070
Initial break address:         0x9858000
First variables on stack:     0xbfdb9b43
Relative position of global (0x804a030):
	Before the break
	Before the end of the BSS segment
	After the end of the data segment
	After the end of the text segment
	Before the first variable on the stack
Relative position of global_char (0x804a01c):
	Before the break
	Before the end of the BSS segment
	Before the end of the data segment
	After the end of the text segment
	Before the first variable on the stack
Relative position of consttr (0x8048ac7):
	Before the break
	Before the end of the BSS segment
	Before the end of the data segment
	After the end of the text segment
	Before the first variable on the stack
Relative position of local (0xbfdb9b03):
	After the break
	After the end of the BSS segment
	After the end of the data segment
	After the end of the text segment
	Before the first variable on the stack
Relative position of heap (0x9858008):
	After the break
	After the end of the BSS segment
	After the end of the data segment
	After the end of the text segment
	Before the first variable on the stack

• Compléter l'ensemble du code pour obtenir la même sortie. N'oubliez pas les problèmes de header.

Prémisses pour l'organisation du tas

Lorsque nous nous intéresseront à l'implémentation d'un malloc(3) simple, nous auront besoin de faire quelques manipulations sur des listes doublement-chaînées, possiblement circulaires. Nous allons donc nous entraîner.

Doublement-Chaînées et circulaires

Nous voulons une structure telle que:

• doublement-chaînée: chaque élément est lié à son successeur et son prédécesseur.
• circulaire: le successeur du dernier élément correspond au premier élément et respectivement le prédécesseur du premier élément correspond au dernier élément.
• insertion en fin: l'insertion doit toujours avoir lieu entre le dernier et le premier élément.

Nous allons avoir deux structures: les éléments de la liste et la sentinelle contenant le pointeur courrant (nous verrons son usage plus tard) et le pointeur sur le plus ancien élément (le premier.)

Voici les structures en question:

typedef struct s_sent  *list;
 
struct s_cell {
  struct s_cell        *next, *prev;
  int                   value;
};
 
struct s_sent {
  struct s_cell        *base, *current;
};

• Écrire les fonctions suivantes:

/* new_list() returns a newy allocated empty list */
list new_list(void);
 
/* is_empty(l) return true (not 0) if l is not an empty list */
/* pre-condition: l != NULL */
int is_empty(list l);
 
/* insert(l,x) insert la valeur x en fin de liste */
/* pre-condition: l != NULL et x n'est pas dans la liste */
/* post-condition: l->base->prev->value == x */
void insert(list l, int x);

Recherche

Nous allons maintenant faire une recherche dans la liste. Bien évidement, le problème principal pour une liste circulaire est de ne pas chercher infiniment …

Nous allons utiliser le pointeur current pour la recherche. Celui-ci est initialement NULL et dans ce cas, on l'initialise à la même valeur que le champ base. Lorsque l'on trouve un élément, le pointeur current prend la valeur du successeur de l'élément trouvé, et si l'élement cherché n'est pas trouvé, il garde la valeur qu'il avait en début de recherche.

La recherche ne portera pas sur une recherche de valeur exact, nous voulons une valeur supérieur ou égale. Nous allons effectuer une recherche de type first-fit, c'est à dire que l'on s'arrêtera dès la première valeur trouvée, alors que dans une recherche de type best-fit nous aurions chercher la plus petite valeur supérieure ou égale.

La fonction de recherche renverra le pointeur sur la cellule contenant la valeur cherchée ou NULL si aucune valeur ne correspond. Bien évidement, si la liste est vide, la fonction renvoie NULL directement.

• Écrire la fonction suivante:

struct s_cell* find_greater(list l, int x);