Voir la source de 2014:01:13:TP:C:Memoires:01

[[category:EPITA:TP:20132014]]

== Introduction ==

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

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

== 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 <tt>sbrk(2)</tt> 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 <tt>sbrk(2)</tt> 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 <tt>0</tt> octets et de récupérer cette adresse.

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

<source lang="C">
void *base() {
  static void  *brk_base;
  if (!brk_base)
    brk_base = sbrk(0);
  return brk_base;
}
</source>

Attention, pour être sûr que l'adresse obtenue soit correcte, il faut s'assurer que cette fonction soit appeler avant tout appelle à <tt>malloc(3)</tt> ou autre. Seulement, voila, toutes (ou presque) les fonctions de <tt>stdio.h</tt> 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 <tt>etext(3)</tt>)
* la fin du segment de donnée (voir <tt>edata(3)</tt>)
* la fin du segment BSS (voir <tt>end(3)</tt>)
* l'adresse initiale du tas (récupérer par notre fonction <tt>base()</tt>.)

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

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

Et maintenant regardons la pile … 

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

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

=== 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 <tt>void locate_ptr(void *p, char *msg)</tt> qui positionne le pointeur <tt>p</tt> 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 <tt>msg</tt> sert uniquement à titre de documentation.'''

Voici une fonction <tt>main()</tt> utilisant nos fonctions:

<source lang="C">
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;
}
</source>

La sortie obtenue, ressemble à ça:

<pre>
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
</pre>

* '''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 <tt>malloc(3)</tt> 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:

<source lang="C">
typedef struct s_sent  *list;

struct s_cell {
  struct s_cell        *next, *prev;
  int                   value;
};

struct s_sent {
  struct s_cell        *base, *current;
};
</source>

* '''Écrire les fonctions suivantes:'''

<source lang="C">
/* 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);
</source>

=== 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 <tt>current</tt> pour la recherche. Celui-ci est initialement <tt>NULL</tt> et dans ce cas, on l'initialise à la même valeur que le champ <tt>base</tt>. Lorsque l'on trouve un élément, le pointeur <tt>current</tt> 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 <tt>NULL</tt> si aucune valeur ne correspond. Bien évidement, si la liste est vide, la fonction renvoie <tt>NULL</tt> directement.

* '''Écrire la fonction suivante:'''
<source lang="C">
struct s_cell* find_greater(list l, int x);
</source>