2014:01:20:TP:C:Memoires:Malloc

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 malloc(3).

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

• malloc(3)
• sbrk(2)
• errno(2)

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 malloc(3), typiquement printf(3), err(3) ou perror(3). En conséquent, si vous êtes amené à faire des affichages, il faudra utiliser write(2) et bien évidement vous utiliserez de préférence le débogueur gdb(1).

Forme du rendu

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

• login-tp20140120
  • AUTHORS
  • Makefile
  • malloc.c

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

Le rendu est ouvert ici: [1]

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

Premier pas avec sbrk(2)

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

void *dummy_alloc(size_t s)

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

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

#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;
}

Implémentation de malloc

Outils

Alignement

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

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

Structure

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

struct chunk {
  struct chunk *next, *prev;
  size_t        size;
  int           free;
  void         *data; // pointer to data
};

Base

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

static
void *base() {
  static struct chunk  *b = NULL;
  // FIX ME
  return b;
}

Lors du premier appel de la fonction, il faudra:

• initialiser b à l'adresse de départ du tas (voir sbrk(2))
• 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.)

/*
 * 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);

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 sbrk(2)); 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 (sbrk(2) renvoie (void*)(-1)) pour un problème de mémoire disponible (errno == ENOMEM) la fonction renverra NULL. Pour toutes les autres échecs, vous terminerez le programme avec la fonction _exit(2) et le code de retour 71.

/*
 * 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);

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)

void *malloc(size_t s);

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.

void free(void *p);

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.)

void *calloc(size_t n, size_t size);
void *realloc(void *old, size_t size);

Construire une bibliothèque

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

La compilation se fait en deux étapes:

• produire le le fichier .o
• transformer le fichier .o en .so

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

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

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

Et comment tester ? Et bien, c'est tout simple, vous pouvez ajouter à votre environnement la variable LD_PRELOAD 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.)

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

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.