Voir la source de 2014:01:20:TP:C:Memoires:Malloc

[[category:EPITA:TP:20132014]]

== Introduction ==

'''Ce TP est prévu pour deux semaines et un rendu aura lieu après la deuxième séance. Les informations arriveront plus tard.'''

L'objectif de ce TP est réaliser une implémentation simple, mais fonctionnelle, de <tt>malloc(3)</tt>.

Dans un premier temps, je vous conseille de lire les pages de manuels suivantes:

* <tt>malloc(3)</tt>
* <tt>sbrk(2)</tt>
* <tt>errno(2)</tt>

'''Attention:''' dans la suite nous allons essayer d'écrire notre propre allocateur, celui-ci va probablement interférer avec celui de la bibliothèque standard. En conséquence, vous ne pourrez pas utiliser les fonctions qui utilisent <tt>malloc(3)</tt>, typiquement <tt>printf(3)</tt>, <tt>err(3)</tt> ou <tt>perror(3)</tt>. En conséquent, si vous êtes amené à faire des affichages, il faudra utiliser <tt>write(2)</tt> et bien évidement vous utiliserez de préférence le débogueur <tt>gdb(1)</tt>.

=== Forme du rendu ===

Le suffixe de rendu est <tt>tp20140120</tt> est votre archive (<tt>login-tp20140120.tar.bz2</tt>) devra contenir:

* <tt>login-tp20140120</tt>
** <tt>AUTHORS</tt>
** <tt>Makefile</tt>
** <tt>malloc.c</tt>

Votre <tt>Makefile</tt> devra fournir les règles pour produire les fichiers: <tt>malloc.o</tt> et <tt>libmalloc.so</tt> (voir la fin du sujet.) La compilation devra se faire avec au moins les ''flags'' suivants: <tt>-Wall -Wextra -std=c99 -O2</tt>.

Le rendu est ouvert ici: [http://rendu.infoprepa.epita.fr/EPITA2017/index.php?TP=20140203]

: '''La deadline est prévu pour le lundi 3 février 2014 à 23h42.'''

== Premier pas avec <tt>sbrk(2)</tt> ==

Avant de rentrer dans le vif du sujet, nous allons mettre en place un ''allocateur stupide'' en utilisant juste <tt>sbrk(2)</tt> (comme vu en cours.)

<source lang="C">
void *dummy_alloc(size_t s)
</source>

* '''Écrire la fonction <tt>dummy_alloc(s)</tt> qui ''alloue'' une zone mémoire de <tt>s</tt> octets en déplaçant le ''break'' de la taille demandée. Si le déplacement échoue avec le code d'erreur <tt>ENOMEM</tt> dans <tt>errno(2)</tt>, la fonction renverra <tt>NULL</tt>, pour les autre erreurs vous quitterez avec la fonction <tt>_exit(2)</tt> (attention, pas <tt>exit(3)</tt>) et le code de retour 127.'''

Voici un programme de tests, vous noterez la variable <tt>last</tt> (déclarer en volatile pour être sûr que les modifications soient effective.)

<source lang="C">
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>

void *dummy_alloc(size_t s) {
  // FIX ME
  return NULL;
}


// Testing
int main() {
  char                 *tab[256];
  // keep track of break
  volatile void        *last;
  last = sbrk(0);
  for (unsigned i=0; i < 256; ++i) {
    tab[i] = dummy_alloc(16);
    last = sbrk(0);
    for (unsigned j=0; j < 15; ++j)
      tab[i][j] = 'a' + (i%26);
    tab[i][15] = '\n';
    write(STDOUT_FILENO, tab[i], 16);
  }
  return 0;
}
</source>

== Implémentation de malloc ==

=== Outils ===

==== Alignement ====

Il vous faut une macro pour aligner des valeurs sur la taille de <tt>size_t</tt> (<tt>sizeof (size_t)</tt>).

* '''Écrire une fonction <tt>word_align</tt> qui aligne un entier sur le multiple de <tt>sizeof (size_t)</tt> immédiatement suivant. Votre fonction devra être déclarée comme <tt>static inline</tt>'''

==== Structure ====

Nous utiliserons la structure de donnée suivante pour gérer les méta-données.

<source lang="C">
struct chunk {
  struct chunk *next, *prev;
  size_t        size;
  int           free;
  void         *data; // pointer to data
};
</source>

==== Base ====

Pour récupérer le début du tas nous allons mettre en place la fonction <tt>base()</tt> qui sauvera l'adresse de départ du tas dans une variable locale statique.

<source lang="C">
static
void *base() {
  static struct chunk  *b = NULL;
  // FIX ME
  return b;
}
</source>

Lors du premier appel de la fonction, il faudra:

* initialiser <tt>b</tt> à l'adresse de départ du tas (voir <tt>sbrk(2)</tt>)
* créer une sentinelle en début de tas: un bloc de taille 0 avec seulement les méta-données. Ce bloc sera marqué comme occupé.
* ''bonus'': on pourra vérifier que l'adresse de début de tas est bien alignée.

=== Recherche ===

On va maintenant chercher un bloc libre de la bonne taille.

Dans le cas où aucun bloc n'est disponible, nous auront besoin (dans la suite) d'ajouter un nouveau bloc à la fin, ce qui nécessite de disposer d'un pointeur sur le dernier bloc. C'est pourquoi la fonction de recherche renseignera également un pointeur (passé par adresse) qui contiendra l'adresse du bloc précédant (le dernier bloc, dans le cas d'une recherche infructueuse.)

<source lang="C">
/*
 * find(s,heap) search for a block of size less or equal to s
 * returns the pointer to meta data, or NULL if none found
 * s is supposed to be already align to word size
 * heap is a pointer to the pointer of the first heap block
 * heap will store a pointer to the block preceding the returned block
 */
struct chunk *find(size_t s, struct chunk **heap);
</source>

Vous implémenterez un recherche ''first-fit'': votre fonction renverra le premier bloc faisant l'affaire (même s'il est trop grand.)

=== Extension du tas ===

Lorsqu'aucun bloc libre n'a été trouvé, il nous faut étendre le tas. Le principe est simple: on ajoute la taille voulue plus la taille des méta-données à la fin du tas (avec <tt>sbrk(2)</tt>); on s'assure que le nouveau bloc soit attaché avec les autres (comme suivant de l'ancien dernier bloc.)

Si l'extension du tas échoue (<tt>sbrk(2)</tt> renvoie <tt>(void*)(-1)</tt>) pour un problème de mémoire disponible (<tt>errno == ENOMEM</tt>) la fonction renverra <tt>NULL</tt>. Pour toutes les autres échecs, vous terminerez le programme avec la fonction <tt>_exit(2)</tt> et le code de retour <tt>71</tt>.

<source lang="C">
/*
 * new_chunk(s,prev)
 * extends the heap by s + sizeof (struct chunk) bytes
 * returns pointers to the meta-data chunk
 * link the meta-data chunk to the last block pointed by prev
 * returns NULL if sbrk fails for ENOMEM, _exit(71) otherwise.
 */
struct chunk *new_chunk(size_t s, struct chunk *prev);
</source>

=== Première version de malloc ===

On peut maintenant regrouper les fonctions précédantes pour écrire une première version de malloc.

Votre fonction devra:

* récupérer la base
* chercher un bloc libre
* si besoin étendre le tas
* renvoyer le pointeur sur les données (pas les méta-données)

<source lang="C">
void *malloc(size_t s);
</source>

=== free ===

L'objectif est maintenant de libérer les blocs alloués via malloc.

Dans un premier temps, vous devez retrouver le pointeur sur les méta-données du bloc (en effectuant un minimum de vérification.) Ensuite, il suffira de marquer le bloc comme étant libre.

<source lang="C">
void free(void *p);
</source>

== Extension ==

=== Split ===

Le but est d'étendre malloc pour qu'il coupe les blocs alloué lorsque ceux-ci sont trop grands.

=== Merge ===

Le but est d'étendre free pour qu'il fusionne le bloc suivant et/ou le précédant.

=== Retour de la mémoire au système ===

Le but est d'étendre free de manière à ce que lorsqu'il libère le dernier bloc du tas, il déplace le break pour rendre la mémoire au système.

Le seul bloc qu'il faudra toujours préserver est la sentinelle.

== Autres fonctions ==

Vous pouvez compléter votre malloc avec les autres fonctions associées (voir les pages de manuel pour la spécification exacte.)

<source lang="C">
void *calloc(size_t n, size_t size);
void *realloc(void *old, size_t size);
</source>

== Construire une bibliothèque ==

Pour tester, nous pourrions construire une bibliothèque dynamique pour remplacer l'implémentation de <tt>malloc(3)</tt> de la bibliothèque standard.

La compilation se fait en deux étapes:
* produire le le fichier <tt>.o</tt>
* transformer le fichier <tt>.o</tt> en <tt>.so</tt>

Supposons que votre code se trouve dans le fichier <tt>malloc.c</tt> voici la séquence de compilation pour produire <tt>libmalloc.so</tt>:

<pre>
> clang -Wall -Wextra -std=c99 -fPIC -c -o malloc.o malloc.c
> clang -shared -o libmalloc.so malloc.o
</pre>

On notera l'option <tt>-fPIC</tt> lors de la production du <tt>.o</tt> et l'option <tt>-shared</tt> pour produire la bibliothèque partagée.

Et comment tester ? Et bien, c'est tout simple, vous pouvez ajouter à votre environnement la variable <tt>LD_PRELOAD</tt> qui contiendra le chemin vers une bibliothèque partagée qui sera chargée à l'exécution de tous vos binaires.

'''Attention:''' si vous préchargez votre malloc, tout les programmes lancés depuis le shell courrant utiliseront votre malloc. Vous devez donc fournir également free, calloc et realloc avant de pouvoir faire ça. Un bonne idée serait de démarrer un shell séparé pour pouvoir le quitter et le relancer facilement. Voici une petite session en exemple (avec un malloc incomplet.)

<pre>
> clang -Wall -Wextra -std=c99 -fPIC -c -o malloc.o malloc.c
> clang -shared -o libmalloc.so malloc.o
> zsh # my own shell
> export LD_PRELOAD=./libmalloc.so
> /bin/ls
[1]    2597 segmentation fault (core dumped)  /bin/ls
> ^D
>
</pre>

Le fait de travailler avec shell séparé, permet de quitter simplement le shell ''cassé'' (tout ce qui n'est pas ''builtin'' du shell risque de planter à cause de votre malloc) sans perdre votre terminal de travail.