TP3: Allocateur de mémoire dynamique

Le but de ce TP est de réécrire les fonctions d'allocation dynamique de la bibliothèque standard: malloc(), free(), calloc() et realloc(). Vous avez évidemment étudié et utilisé ces fonctions, ou au moins les deux premières; si vous avez quelques lacunes, un coup de man -S 3 malloc vous renseignera.

La réalisation de telles fonctions peut être extrêmement dépendante du système d'exploitation pour être efficace. Pour ce TP sous Linux, on s'appuiera sur la fonction sbrk(): lisez la page de manuel correspondante. Celle-ci est jugée obsolète dans les versions récentes de la norme POSIX: à la place, on recommande malloc(), qui est plus flexible. C'est-à-dire que quand on utilise la bibliothèque standard pour écrire des programmes portables, on doit utiliser malloc() et pas sbrk().

Dans ce TP, cependant, l'objectif est différent: on veut réécrire des fonctions de la bibliothèque standard; il est donc légitime d'utiliser des fonctions de bas niveau. La fonction sbrk() repose sur l'appel système le moins coûteux et le plus simple sous Linux pour demander de la mémoire au système: brk(). Ces deux fonctions sont déclarées dans l'en-tête unistd.h. Consultez la page de manuel de ces fonctions avant de commencer: man -S 2 brk.

Note:

Comme on réécrit les fonctions d'allocation de la bibliothèque standard, il faut se garder de les utiliser. Votre code ne doit donc pas faire appel à des fonctions qui utilisent malloc(), free() et compagnie, même indirectement, au risque d'introduire une dépendance cyclique. C'est le cas par exemple des fonctions de la bibliothèque stdio.h (printf() et consorts). Pour afficher des messages, on utilisera plutôt les fonctions définies dans les fichiers affiche.h et affiche.c fournis.
Dans le code de votre allocateur, les deux seules inclusions de sources autorisées sont celle qui déclare sbrk() et celle qui déclare les fonctions d'affichage:

#include <unistd.h>
#include "affiche.h"

Objectifs et évaluation

On ne vous demandera pas de compte-rendu: des fichiers sources bien commentés et intelligemment structurés, ainsi qu'un choix de noms pertinents pour vos fonctions, variables, types, etc. devraient suffire à rendre votre code lisible et compréhensible.

Vous coderez votre allocateur dans des fichiers alloc.h et alloc.c. Le fichier d'en-têtes alloc.h ne contiendra pas forcément les déclarations de toutes les variables et fonctions demandées ci-dessous, seulement celles qui doivent être accessibles à l'utilisateur pour:

• utiliser malloc() et ses amis;
• contrôler le comportement de l'allocateur (les stratégies d'allocation et les différents seuils et limites);
• afficher les statistiques.

En plus de l'allocateur, vous écrirez quelques programmes de test simples, en essayant de mettre en évidence des cas dans lesquels des stratégies d'allocation différentes produisent des effets différents. Les sources de ces tests sont à joindre à votre projet. Vous fournirez un Makefile permettant de compiler ces programmes de test facilement.

Testez également la compatibilité votre code avec des programmes qui n'ont pas été explicitement écrits pour ce TP, mais qui utilisent malloc(), free(), calloc() et/ou realloc(). Par exemple vous pourrez récuperer les sources de programmes en C qui utilisent l'allocation dynamique, que vous avez pu étudier ou écrire vous même au cours de votre cursus.

Vous fournirez tous les fichiers sources (*.c, *.h et Makefile) de votre projet dans une archive obligatoirement au format tar.gz ou tar.bz2 et avec un nom explicite: par exemple INFO-502_TP3_Nom1-Nom2.tar.gz pour un binôme Nom1-Nom2. Cette archive est à transmettre par e-mail à votre encadrant de TP: Thibault Carron, Pierre Hyvernat ou Lionel Vaux, à l'adresse habituelle ( Nom.Prenom@univ-savoie.fr).

La notation prendra en compte la correction de votre code, évidemment, mais également sa lisibilité et sa modularité. L'écriture de toute fonction auxiliaire qui vous parait utile est encouragée.

Toute erreur à la compilation sera lourdement sanctionnée. Les options du compilateur renseignées dans le Makefile doivent comprendre au moins -Wall et -Werrors. C'est-à-dire qu'un avertissement sera également considéré comme une erreur.

Blocs alloués et liste de blocs libres

Le principe général de l'allocateur mémoire est de maintenir une liste de blocs libres de mémoire allouée. Quand l'utilisateur demande un bloc de taille taille, on cherche dans la liste un bloc libre de taille au moins taille. Le bloc obtenu dépend de la stratégie utilisée: on considèrera les stratégies first fit, best fit, worst fit ou next fit. Si aucun bloc libre n'est assez grand, on fait un appel à sbrk() pour créer un nouveau bloc libre. La liste des blocs libres est maintenue dans l'ordre croissant des adresses.

Chaque bloc est muni d'un en-tête qui renseigne sur la taille de la zone allouée. De plus, si le bloc est libre, on stocke les adresses des blocs libres précédent et suivant: la liste des blocs libres est cyclique et doublement chaînée. On partira des définitions de types suivantes:

struct alloc_entete {
        size_t taille ;
        struct alloc_entete *prec ;
        struct alloc_entete *suiv ;
} ;
typedef struct alloc_entete *alloc_bloc_t ;

On déclarera des variables globales alloc_premier_bloc_libre et alloc_bloc_suivant_pour_nextfit de type alloc_bloc_t.

Note:

Le type size_t est normalement défini par l'inclusion de l'en-tête unistd.h mentionné plus haut.

Tâche 1

• Écrivez des fonctions

  alloc_bloc_t alloc_cherche_firstfit(size_t taille) ; 
  alloc_bloc_t alloc_cherche_bestfit(size_t taille) ; 
  alloc_bloc_t alloc_cherche_worstfit(size_t taille) ; 
  alloc_bloc_t alloc_cherche_nextfit(size_t taille) ; 
  

  qui renvoient chacune l'adresse du bloc libre de taille au moins taille obtenu en suivant la stratégie correspondante, ou NULL s'il n'y en a pas.

Données des blocs utilisés

Soit la déclaration:

alloc_bloc_t b ; 

Le pointeur b représente un bloc d'allocation composé d'un en-tête et d'une zone allouée. Cette zone contient exactement b->taille octets.

Notez que l'adresse de la zone mémoire allouée n'est pas renseignée directement dans la structure struct alloc_entete: l'idée est que cette zone commence juste après le champ taille du struct alloc_entete correspondant, c'est à dire à l'adresse de b->prec. Cette méthode est contre-intuitive: la zone de données empiète sur les champs du struct alloc_entete. Elle est cependant efficace: on ne perd que la taille d'un size_t (ou un peu plus suivant les exigences d'alignement de l'architecture) dans l'en-tête d'un bloc occupé. C'est-à-dire que la taille en mémoire du bloc lui-même serait plutôt sizeof(b->taille)+b->taille, considérations d'alignement mises à part. Dans un bloc libre, la zone de données n'est pas utilisée; on a donc toute latitude pour l'occuper à des fins internes, avec les champs prec et suiv.

On a donc les deux situations suivantes pour la représentation des blocs en mémoire.

Bloc occupé

Si le bloc b est occupé (la zone a été attribuée par un malloc()):

Les champs b->prec et b->suiv sont masqués par la zone de données: on ne s'en sert pas de toute façon, puisque le bloc n'est plus dans la liste des blocs libres.

Bloc libre

Si le bloc b est libre:

En particulier, il est nécessaire que la taille soit toujours suffisante pour stocker au moins les deux pointeurs prec et suiv: cette remarque sera importante par la suite.

Tâche 2

• Écrivez une fonction

  void *alloc_bloc_mem(alloc_bloc_t b) ; 
  

  qui renvoie un pointeur vers le début de la zone de données du bloc b (en supposant qu'il est alloué). Par définition, c'est pareil que l'adresse de b->prec.
• Écrivez une fonction

  alloc_bloc_t alloc_bloc_entete(void *p) ;
  

  qui renvoie l'adresse du bloc d'information associé à la zone de mémoire pointée par p (c'est l'inverse de la précédente): si b est de type alloc_bloc_t, alors on doit avoir b==alloc_bloc_entete(alloc_bloc_mem(b)); réciproquement, si p est de type void *, alors p==alloc_bloc_mem(alloc_bloc_entete(p)).

Notez qu'une fois le premier point réalisé, le deuxième s'en déduit directement avec un peu d'arithmétique de pointeurs.

malloc()

Le comportement de votre allocateur doit dépendre de la stratégie choisie. On ajoutera la définition de type suivante:

typedef enum { 
        ALLOC_FIRSTFIT, 
        ALLOC_BESTFIT,
        ALLOC_WORSTFIT, 
        ALLOC_NEXTFIT 
} alloc_strategie_t ;

et on déclarera une variable globale alloc_strategie_courante de ce type.

Quand on veut allouer une zone pour l'utilisateur, il faut d'abord chercher un bloc libre dans lequel l'insérer (ou en fabriquer un nouveau). Puis on sépare éventuellement le bloc en deux, si la taille demandée par l'utilisateur est sensiblement inférieure à la taille du bloc libre trouvé. On ajoutera une variable globale alloc_taille_min qui définit la taille minimale d'un bloc libre: si pour couper un bloc libre en deux (pour donner la première partie à l'utilisateur), il fallait créer un bloc de taille inférieure, on donnerait plutôt tout le bloc libre initial à l'utilisateur. On s'assurera du fait que alloc_taille_min est toujours au moins suffisante pour stocker les deux pointeurs prec et suiv d'un bloc libre.

Tâche 3

• Écrivez une fonction

  void *alloc_occupe(alloc_bloc_t cible, size_t taille) ;
  

  qui, en supposant que le bloc cible est libre et de taille au moins taille effectue les opérations suivantes:
  • coupe le bloc cible en deux blocs contigus si c'est pertinent;
  • met à jour les pointeurs de la liste doublement chaînée des blocs libres;
  • renvoie l'adresse de la zone de mémoire du bloc nouvellement occupé (avec la fonction alloc_bloc_mem() évidemment).
• Écrivez la fonction

  void *malloc(size_t taille) ;
  

  qui effectue les opérations suivantes:
  • recherche le bloc libre de taille au moins taille suivant la stratégie définie par alloc_strategie_courante;
  • en cas d'échec, fait un appel à sbrk() pour obtenir au moins autant de mémoire que nécessaire (on pourra demander plus, si on pense cette méthode plus efficace: penser à tester) et construit un bloc libre avec cette nouvelle zone de mémoire;
  • appelle alloc_occupe();
  • mémorise l'adresse du bloc libre qui suit celui qu'on vient d'occuper dans alloc_bloc_suivant_pour_nextfit.
• Écrivez la fonction

  void *calloc(size_t nmemb, size_t size) ;
  

  à partir de la précédente.

free()

Quand on libère un bloc, il faut le réinsérer dans la liste des blocs libres. On rappelle que la liste est triée par ordre croissant des adresses. De plus, si le bloc libre précédent (ou suivant) est immédiatement avant (ou après) le bloc libéré, on a tout intérêt à les fusionner pour former un bloc libre plus gros et éviter la fragmentation.

Si le bloc qu'on libère est le dernier bloc alloué (juste avant la limite du segment de données obtenue avec sbrk(0)), on est dans un cas spécial: on peut restituer la mémoire libérée au système, plus tôt que de créer un bloc libre.

Tâche 4

• Écrivez une fonction

  void alloc_fusion(alloc_bloc_t b) ;
  

  qui, en supposant que b est dans la liste des blocs libres, fusionne b avec b->suiv s'ils sont contigus.
• Écrivez une fonction

  void free(void *p) ;
  

  qui effectue les opérations suivantes:
  • calcule l'adresse b de l'en-tête du bloc dont les données commencent au pointeur p;
  • insère b dans la liste des blocs libres;
  • fait les fusions pertinentes dans le bon ordre.
• Modifiez cette fonction pour appeler sbrk() avec un argument négatif et restituer de la mémoire au système quand on libère le dernier bloc: dans ce cas, on n'insère pas ce bloc dans la liste des blocs libres.

realloc()

À partir de malloc() et free(), on peut facilement écrire realloc() de manière naïve: allouer un nouveau bloc, copier les données, et libérer l'ancien bloc. Évidemment, on peut faire mieux dans certains cas:

• si la réallocation est à la baisse, ou si la taille de la zone allouée reste suffisante, on peut rester dans le même bloc;
• si la taille diminue beaucoup, on peut même scinder le bloc pour former un nouveau bloc libre avec l'espace restant;
• quand la zone à réallouer est celle du dernier bloc, on est dans un cas spécial, car on peut librement augmenter la taille de cette zone avec sbrk(), sans riquer d'écraser un autre bloc alloué.

Tâche 5

• Écrivez une fonction

  void *realloc(void *ptr, size_t taille) ;
  

  qui teste si la taille du bloc courant reste suffisante et qui ne fait un appel à malloc() et un appel à free() que si c'est nécessaire.
• Réécrivez cette fonction pour scinder le bloc courant quand la différence entre la taille du bloc et la taille demandée dépasse un certain seuil (introduisez une variable globale alloc_seuil_scinde).
• Ajoutez un cas supplémentaire: si on est dans le dernier bloc, et qu'il est d'une taille insuffisante, on appelle sbrk() et on augmente la taille de la zone allouée du dernier bloc.

Statistiques

On veut maintenant pouvoir collecter des informations sur le fonctionnement de l'allocateur:

• le nombre actuel de blocs;
• le nombre actuel de blocs libres;
• le nombre actuel d'octets alloués par les appels à sbrk();
• le nombre total de demandes d'occupation de blocs (par malloc() ou les cas pertinents de realloc());
• le nombre total de blocs fusionnés;
• le nombre total de blocs scindés;
• le nombre total d'appels à sbrk().

Tâche 6

• Mettez en place l'infrastructure nécessaire pour collecter les statistiques et écrivez une fonction

  void alloc_info() ;
  

  qui les affiche.

Souvenez-vous que cette fonction ne peut pas utiliser printf() ni les fonctions de stdio.h en général, seulement les fonctions de affiche.h et celles que vous avez vous-même définies.

Tests

Rappelez-vous que vous devez tester vos fonctions !

Bien que cette tâche figure en dernière position, vous devriez avoir le réflexe de faire le premier item de ce qui suit avant même qu'on vous le demande. On ne le rappelle que pour enfoncer le clou.

Tâche 7

• Écrivez d'abord de petits programmes simples, qui enchaînent les allocations/désallocations, en utilisant uniquement les fonctions de alloc.h et affiche.h. Assurez-vous que votre allocateur n'a pas un comportement aberrant.
• Testez ensuite des programmes simples qui utilisent les fonctions d'affichage de la bibliothèque standard, par exemple printf(). Regardez ce que donnent vos statistiques.
• Puis testez quelque chose d'un peu plus conséquent, par exemple un programme complet vu dans un autre cours, avec des structures de données dynamiques (listes, arbres, graphes, buffers de données, etc.).