4  Bibliothèque d’allocation mémoire – bam

La phase ultime de ce projet est de développer une bibliothèque de remplacement des fonctions d’allocation dynamique fournies par la bibliothèque standard.

4.1  Bibliothèque et appels système

La bibliothèque Unix propose un système d’allocation dynamique de mémoire principalement utilisé au travers les fonctions malloc() et free(). Il existe aussi un appel système d’allocation de mémoire sbrk() [On se contentera de l’explication sommaire suivante : un appel système est un appel d’une fonction de bas niveau du système. La notion d’appel système sera détaillée dans le cours de « Programmation des systèmes » de 3e année de licence. Par ailleurs, l’emploi de sbrk() est maintenant obsolète ; on s’en accommodera dans le cadre de ce projet pour ne pas compliquer les choses.].

Les fonctions de la bibliothèque sont implémentées au dessus des appels système. Les fonctions malloc() et free() sont donc implémentées à l’aide d’appels à sbrk().

Détaillons ces trois fonctions.

void *malloc (unsigned size);

La fonction malloc() de la bibliothèque retourne un pointeur sur une zone mémoire d’au moins size octets, qui est correctement aligné selon la contrainte la plus forte de tous les types manipulables en C.

void free (void *ptr);

La fonction free() de la bibliothèque libère une zone précédemment allouée ; ptr est un pointeur sur cette zone.

void *sbrk (int incr);

L’appel système sbrk() incrémente l’espace mémoire utilisateur de incr octets et retourne un pointeur sur le début de cette zone nouvellement allouée.

Le principe de fonctionnement est le suivant :

• l’utilisateur demande une zone mémoire via un appel à malloc() ;
• malloc() demande lui même une zone mémoire au système via sbrk(). Pour éviter le coût de cet appel système, malloc() demande un « grande » zone mémoire à sbrk() et n’en utilise qu’une partie pour satisfaire la demande de l’utilisateur. Une structure de données interne à la bibliothèque d’allocation mémoire conserve la zone mémoire obtenue et non utilisée ;
• lors de prochaines demandes de blocs mémoire par l’utilisateur via des appels à malloc(), la mémoire excédentaire précédemment obtenue par sbrk() est utilisée ;
• les blocs mémoire libérés par free() sont gardés dans l’espace mémoire utilisateur et pourront aussi servir à répondre aux demandes suivantes. La mémoire n’est jamais rendue au système avant la fin de l’exécution du programme.

4.2  Possible implémentation de malloc()/free()

Comparé à nos allocateurs précédents, notre bibliothèque bam :

• n’utilise plus de tableau alloué statiquement (le tableau membloc), mais les résultats d’appels à sbrk() pour allouer les zones mémoire ;
• permet l’allocation de zones mémoire dont la taille n’est plus exprimée en nombre de blocs, mais en octets.

Le maintien de la liste des zones mémoire libres se fera cependant selon une méthode proche de notre allocateur amb.

L’ensemble des zones mémoire libres est par exemple gardé par la bibliothèque d’allocation mémoire sous la forme d’une liste chaînée :

• chaque zone contient une taille et un pointeur sur la zone suivante, ces deux informations formant en quelque sorte un entête. Cet entête est suivi de la zone mémoire disponible proprement dite ;
• quand une zone mémoire est retournée par malloc(), on conserve la taille de cette zone dans l’entête.

L’implémentation de malloc() peut parcourir la liste des zones libres jusqu’à rencontrer une zone suffisamment grande (« first-fit ») pour la zoné mémoire et le nécessaire entête. Si la zone a exactement la taille demandée, on l’enlève de la liste et on la retourne à l’utilisateur. Si la zone est trop grande, on la divise et on retourne à l’utilisateur une zone de la taille demandée ; le reste de la zone est gardée dans la liste des zones libres. Si la recherche d’une zone de taille suffisante a échoué, on demande une augmentation de la mémoire utilisateur au système.

La libération d’une zone mémoire par free() ajoute simplement cette zone mémoire à la liste des zones mémoire libres.