Dans ce dernier chapitre, nous allons mettre en œuvre une partie des notions présentées dans cette partie afin de réaliser un allocateur statique de mémoire.
- Objectif
- Première étape : allouer de la mémoire
- Correction
- Deuxième étape : libérer de la mémoire
- Correction
- Troisième étape : fragmentation et défragmentation
- Correction
Objectif
Votre objectif sera de parvenir à réaliser un petit allocateur statique de mémoire en mettant en œuvre deux fonctions : static_malloc() et static_free() comparables aux fonctions malloc() et free() de la bibliothèque standard. Toutefois, afin d’éviter d’entrer dans les méandres de l’allocation dynamique de mémoire, ces fonctions fourniront de la mémoire préalablement allouée statiquement.
Première étape : allouer de la mémoire
Pour commencer, vous allez devoir construire une fonction static_malloc() dont le prototype sera le suivant.
void *static_malloc(size_t taille);
À la lumière de la fonction malloc(), celle-ci reçoit une taille en multiplet et retourne un pointeur vers un bloc de mémoire d’au moins la taille demandée ou un pointeur nul s’il n’y a plus de mémoire disponible.
Mémoire statique
Afin de réaliser ses allocations, la fonction static_malloc() ira piocher dans un bloc de mémoire statique. Celui-ci consistera simplement en un tableau de char de classe de stockage statique d’une taille prédéterminée. Pour cet exercice, nous partirons avec un bloc de un mébimultiplets, soit 1.048.576 multiplets (1024 × 1024).
static char mem[1048576UL];
Alignement
Toutefois, retourner un bloc de char de la taille demandée ne suffit pas. En effet, si nous allouons par exemple treize multiplets, disons pour une chaîne de caractères, puis quatre multiplets pour un int, nous allons retourner une adresse qui ne respecte potentiellement pas l’alignement requis par le type int. Étant donné que la fonction static_malloc() ne connaît pas les contraintes d’alignements que doit respecter l’objet qui sera stocké dans le bloc qu’elle fournit, elle doit retourner un bloc respectant les contraintes les plus strictes. Dit autrement, la taille de chaque bloc devra être un multiple de l’alignement le plus rigoureux.
Cet alignement peut être connu à l’aide de l’opérateur _Alignof et du type spécial max_align_t (définit dans l’en-tête <stddef.h>).
#include <stddef.h>
#include <stdio.h>
int
main(void)
{
printf("L'alignement le plus strict est : %zu\n", _Alignof(max_align_t));
return 0;
}
L'alignement le plus strict est : 16
Mais… ce n’est pas tout ! Le tableau alloué statiquement doit lui aussi être aligné suivant l’alignement le plus sévère. En effet, si celui-ci commence à une adresse non multiple de cet alignement, notre stratégie précédente tombe à l’eau. Pour ce faire, nous pouvons utiliser le spécificateur _Alignas qui permet de modifier les contraintes d’alignement d’un type1.
static _Alignas(max_align_t) char mem[1048576UL];
Ici nous indiquons donc que nous souhaitons que le tableau mem ait le même alignement que le type max_align_t, soit l’alignement le plus sévère.
Avec ceci, vous devriez pouvoir réaliser la fonction static_malloc() sans encombre.
Hop hop ! Au travail ! 
- Le spécificateur
_Alignasa été introduit par la norme C11. Auparavant, pour modifier l’alignement d’un type, il était nécessaire d’employer une union comprenant un champ de ce type et un champ du type dont on souhaite copier l’alignement. Pour obtenir l’alignement le plus strict, la même technique était employée, mais en utilisant les types avec les alignements les plus sévères (commelong double,long longetvoid *).↩
Correction
#include <assert.h>
#include <stddef.h>
#include <stdio.h>
#define MEM_MAX (1024UL * 1024UL)
#define ALIGN_MAX (_Alignof(max_align_t))
static _Alignas(max_align_t) char mem[MEM_MAX];
static size_t calcule_multiple_align_max(size_t);
static void *static_malloc(size_t);
static size_t calcule_multiple_align_max(size_t a)
{
/*
* Calcule le plus petit multiple de l'alignement maximal égal ou supérieur à `a`.
*/
return (a % ALIGN_MAX == 0) ? a : a + ALIGN_MAX - (a % ALIGN_MAX);
}
static void *static_malloc(size_t taille)
{
/*
* Alloue un bloc de mémoire au moins de taille `taille`.
*/
static size_t alloue = 0UL;
void *ret;
assert(taille > 0);
taille = calcule_multiple_align_max(taille);
if (MEM_MAX - alloue < taille)
{
fprintf(stderr, "Il n'y a plus assez de mémoire disponible.\n");
return NULL;
}
ret = &mem[alloue];
alloue += taille;
return ret;
}
La fonction calcule_multiple_align_max() détermine le plus petit multiple de l’alignement maximal égal ou supérieur à a. Celle-ci nous permet d’« arrondir » la taille demandée de sorte que les blocs alloués soit toujours correctement alignés.
La fonction static_malloc() utilise une variable statique : alloue qui représente la quantité de mémoire déjà allouée. Dans le cas où la taille demandée (arrondie au multiple de l’alignement qui lui est égal ou supérieur) n’est pas disponible, un pointeur nul est retourné. Sinon, la variable alloue est mise à jour et un pointeur vers la position courante du tableau mem est retourné.
Notez que nous avons utilisé une assertion afin d’éviter qu’une taille nulle ne soit fournie.
Deuxième étape : libérer de la mémoire
Pouvoir allouer de la mémoire, c’est bien, mais pouvoir en libérer, ce serait mieux. Parce que pour le moment, dès que l’on arrive à la fin du tableau, que la mémoire précédemment allouée soit encore utilisée ou non, c’est grillé. 
Toutefois, pour mettre en place un système de libération de la mémoire, il va nous falloir changer un peu de tactique.
Ajout d’un en-tête
Tout d’abord, si nous voulons libérer des blocs puis les réutiliser, il nous faut conserver d’une manière ou d’une autre leur taille. En effet, sans cette information, il nous sera impossible de les réaffecter.
Pour ce faire, il nous est possible d’ajouter un en-tête lors de l’allocation d’un bloc, autrement dit un objet (par exemple un entier de type size_t) qui précédera le bloc alloué et contiendra la taille du bloc.
+---------+-----------------+
| En-tête | Bloc alloué |
+---------+-----------------+
Ainsi, lors de l’allocation, il nous suffit de transmettre à l’utilisateur le bloc alloué sans son en-tête à l’aide d’une expression du type (char *)ptr + sizeof (size_t) et, à l’inverse, lorsque l’utilisateur souhaite libérer un bloc, de le récupérer à l’aide d’une expression comme (char *)ptr - sizeof (size_t). Notez que cette technique nous coûte un peu plus de mémoire puisqu’il est nécessaire d’allouer le bloc et l’en-tête.
Les listes chaînées
Mais, ce n’est pas tout. Pour pouvoir retrouver un bloc libéré, il nous faut également un moyen pour les conserver et en parcourir la liste. Afin d’atteindre cet objectif, nous allons employer une structure de donnée appelée une liste chaînée. Celle-ci consiste simplement en une structure comprenant des données ainsi qu’un pointeur vers une structure du même type.
struct list
{
struct list *suivante;
};
Ainsi, il est possible de créer des chaines de structure, chaque maillon de la chaîne référencant le suivant. L’idée pour notre allocateur va être de conserver une liste des blocs libérés, liste qu’il parcourera en vue de rechercher un bloc de taille suffisante avant d’allouer de la mémoire provenant de la réserve. De cette manière, il nous sera possible de réutiliser de la mémoire précédemment allouée avant d’aller puiser dans la réserve.
Nous aurons donc a priori besoin d’une liste comprenant une référence vers le bloc libéré et une référence vers le bloc suivant (il ne nous est pas nécessaire d’employer un membre pour la taille du bloc puisque l’en-tête la contient).
struct bloc
{
void *p;
struct bloc *suivant;
};
Le serpent qui se mange la queue
Cependant, avec une telle technique, nous risquons d’entrer dans un cercle vicieux. En effet, imaginons qu’un utilisateur libère un bloc de 64 multiplets. Pour l’ajouter à la liste des blocs libérés, nous avons besoin d’espace pour stocker une structure bloc, nous allons donc allouer un peu de mémoire. De plus, si par la suite ce bloc est réutilisé, la structure bloc ne nous est plus utile, sauf que si nous la libérons, nous allons devoir allouer une autre structure bloc pour référencé… une structure bloc (à moins que la structure ne s’autoréférence). Voilà qui n’est pas très optimal.
À la place, il nous est possible de recourir à une autre stratégie : inclure la structure bloc dans l’en-tête ou, plus précisémment, son champ suivant, la référence vers le bloc n’étant plus nécessaire dans ce cas. Autrement dit, notre en-tête sera le suivant.
struct bloc
{
size_t taille;
struct bloc *suivant;
};
Lors de la libération du bloc, il nous suffit d’employer le champ suivant de l’en-tête pour ajouter le bloc à la liste des blocs libres.
En-tête En-tête
<-------------------> <------------------->
+---------+---------+-----------------+ +---------+---------+-----------------+
| Taille | Suivant | Bloc alloué | | Taille | Suivant | Bloc alloué |
+---------+---------+-----------------+ +---------+---------+-----------------+
+ ^
| |
+---------------------------------+
Étant donné que l’en-tête précède le bloc alloué, il est impératif que sa taille soit « arrondie » de sorte que les données qui seront stockées dans le bloc respectent l’alignement le plus strict.
Avec ceci, vous devriez pouvoir réaliser une fonction static_free() et modifier la fonction static_malloc() en conséquence. 
Correction
#include <assert.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#define MEM_MAX (1024UL * 1024UL)
#define ALIGN_MAX (_Alignof(max_align_t))
#define MULTIPLE_ALIGN_MAX(a) (size_t)((((a) % ALIGN_MAX) == 0) ? (a) : (a) + ALIGN_MAX - (a) % ALIGN_MAX)
#define TAILLE_EN_TETE MULTIPLE_ALIGN_MAX(sizeof (struct bloc))
struct bloc
{
size_t taille;
struct bloc *suivant;
};
static _Alignas(max_align_t) char mem[MEM_MAX];
static struct bloc *libre;
static void bloc_init(struct bloc *, size_t);
static size_t calcule_multiple_align_max(size_t);
static struct bloc *recherche_bloc_libre(size_t);
static void static_free(void *);
static void *static_malloc(size_t);
static void bloc_init(struct bloc *b, size_t taille)
{
/*
* Initialise les membres d'une structure `bloc`.
*/
b->taille = taille;
b->suivant = NULL;
}
static size_t calcule_multiple_align_max(size_t a)
{
/*
* Calcule le plus petit multiple de l'alignement maximal égal ou supérieur à `a`.
*/
return (a % ALIGN_MAX == 0) ? a : a + ALIGN_MAX - (a % ALIGN_MAX);
}
static struct bloc *recherche_bloc_libre(size_t taille)
{
/*
* Recherche un bloc libre ou une suite de bloc libres dont la taille
* est au moins égale à `taille`.
*/
struct bloc *bloc = libre;
struct bloc *precedent = NULL;
struct bloc *ret = NULL;
while (bloc != NULL)
{
if (bloc->taille >= taille)
{
if (precedent != NULL)
precedent->suivant = bloc->suivant;
else
libre = bloc->suivant;
ret = bloc;
break;
}
precedent = bloc;
bloc = bloc->suivant;
}
return ret;
}
static void *static_malloc(size_t taille)
{
/*
* Alloue un bloc de mémoire au moins de taille `taille`.
*/
static size_t alloue = 0UL;
void *ret;
assert(taille > 0);
taille = calcule_multiple_align_max(taille);
ret = recherche_bloc_libre(taille);
if (ret == NULL)
{
if (MEM_MAX - alloue < TAILLE_EN_TETE + taille)
{
fprintf(stderr, "Il n'y a plus assez de mémoire disponible.\n");
return NULL;
}
ret = &mem[alloue];
alloue += TAILLE_EN_TETE + taille;
bloc_init(ret, taille);
}
return (char *)ret + TAILLE_EN_TETE;
}
static void static_free(void *ptr)
{
/*
* Ajoute le bloc fourni à la liste des blocs libres.
*/
struct bloc *bloc = libre;
struct bloc *nouveau;
if (ptr == NULL)
return;
nouveau = (struct bloc *)((char *)ptr - TAILLE_EN_TETE);
while (bloc != NULL && bloc->suivant != NULL)
bloc = bloc->suivant;
if (bloc == NULL)
libre = nouveau;
else
bloc->suivant = nouveau;
}
Désormais, la fonction static_malloc() fait d’abord appel à la fonction recherche_bloc_libre() avant d’allouer de la mémoire de la réserve. Comme son nom l’indique, cette fonction parcourt la liste des blocs libres à la recherche d’un bloc d’une taille égale ou supérieure à celle demandée. Cette liste est matérialisée par la variable globale libre qui est un pointeur sur une structure de type bloc. Cette variable correspond au premier maillon de la liste et est employée pour initialiser le parcours.
Si aucun bloc libre n’est trouvé, alors la fonction static_malloc() pioche dans la réserve un bloc de la taille demandée augmentée de la taille de l’en-tête. Ces deux tailles sont « arrondies » au multiple égal ou directement supérieur de l’alignement le plus contraignant. Étant donné que la taille de l’en-tête est fixe, nous avons représenté sa taille « arrondie » à l’aide de la macroconstante TAILLE_EN_TETE et de la macrofonction MULTIPLE_ALIGN_MAX (qui réalise le même calcule que la fonction calcule_multiple_align_max(). Une fois le tout alloué, l’en-tête est « retiré » en ajoutant la taille de l’en-tête au pointeur référencant la mémoire allouée et le bloc demandé est retourné.
La fonction static_free() se rend à la fin de la liste et y ajoute le bloc qui lui est fourni en argument. Pour ce faire, elle « récupère » l’en-tête en soustrayant la taille de l’en-tête au pointeur fourni en argument. Notez également que cette fonction n’effectue aucune opération dans le cas où un pointeur nul lui est fourni (tout comme la fonction free() standard), ce qui peut être intéressant pour simplifier la gestion d’erreur dans certains cas.
Troisième étape : fragmentation et défragmentation
Bien, notre allocateur recycle à présent les blocs qu’il a précédemment alloués, c’est une bonne chose. Toutefois, un problème subsiste : la fragmentation de la mémoire allouée, autrement dit sa division en une multitude de petits blocs.
S’il s’agit d’un effet partiellement voulu (nous allouons par petits blocs pour préserver la réserve), il peut avoir des conséquences fâcheuses non désirées. En effet, imaginez que nous ayons alloué toute la mémoire sous forme de blocs de 16, 32 et 64 multiplets, si même tous ces blocs sont libres, notre allocateur retournera un pointeur nul dans le cas d’une demande de par exemple 80 multiplets… Voilà qui est plutôt gênant.
Une solution consiste à défragmenter la liste des blocs libres, c’est-à-dire fusionner plusieurs blocs pour en reconstruire d’autre avec une taille plus importante. Dans notre cas, nous allons mettre en œuvre ce système lors de la recherche d’un bloc libre : désormais, nous allons regarder si un bloc est d’une taille suffisante ou si plusieurs blocs, une fois fusionnés, seront de taille suffisante.
Fusion de blocs
Toutefois, une fusion de blocs n’est possible que si ceux-ci sont adjacents, c’est-à-dire s’ils se suivent en mémoire. Plus précisément, l’adresse suivant le premier bloc à fusionner doit être celle de début du second (autrement dit (char *)ptr_bloc1 + taille_bloc1 == (char *)ptr_bloc2).
Néanmoins, il ne nous est pas possible de vérifier cela facilement si notre liste de blocs libres n’est pas un minimum triée. En effet, sans tri, il nous serait nécessaire de parcourir toute la liste à la recherche d’éventuels blocs adjacents au premier, puis, de faire de même pour le deuxième et ainsi de suite, ce qui n’est pas particulièrement efficace.
À la place, il nous est possible de trier notre liste par adresses croissantes (ou décroissantes, le résultat sera le même) de sorte que si un bloc n’est pas adjacent au suivant, la recherche peut être immédiatement arrêtée pour ce bloc ainsi que tous ceux qui lui étaient adjacents. Ce tri peut être réalisé simplement lors de l’insertion d’un nouveau bloc libre en plaçant celui-ci correctement dans la liste à l’aide de comparaisons : s’il a une adresse inférieure à celle d’un élément de la liste, il est placé avant cet élément, sinon, le parcours continue.
En effet, deux pointeurs peuvent tout à fait être comparés du moment que ceux-ci référencent un même objet ou un même agrégat (c’est notre cas ici puisqu’ils référenceront tous des éléments du tableau mem) et qu’ils sont du même type (une conversion explicite vers le type pointeur sur char sera donc nécessaire comme explicité auparavant).
N’oubliez pas que si deux ou plusieurs blocs sont fusionnés, il n’y a plus besoin que d’un seul en-tête, les autres peuvent donc être comptés comme de la mémoire utilisable.
Correction
#include <assert.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#define MEM_MAX (1024UL * 1024UL)
#define ALIGN_MAX (_Alignof(max_align_t))
#define MULTIPLE_ALIGN_MAX(a) (size_t)((((a) % ALIGN_MAX) == 0) ? (a) : (a) + ALIGN_MAX - (a) % ALIGN_MAX)
#define TAILLE_EN_TETE MULTIPLE_ALIGN_MAX(sizeof (struct bloc))
struct bloc
{
size_t taille;
struct bloc *suivant;
};
struct suite
{
struct bloc *precedent;
struct bloc *premier;
struct bloc *dernier;
size_t taille;
};
static _Alignas(max_align_t) char mem[MEM_MAX];
static struct bloc *libre;
static void bloc_init(struct bloc *, size_t);
static size_t calcule_multiple_align_max(size_t);
static struct bloc *recherche_bloc_libre(size_t);
static void static_free(void *);
static void *static_malloc(size_t);
static void bloc_init(struct bloc *b, size_t taille)
{
/*
* Initialise les membres d'une structure `bloc`.
*/
b->taille = taille;
b->suivant = NULL;
}
static size_t calcule_multiple_align_max(size_t a)
{
/*
* Calcule le plus petit multiple de l'alignement maximal égal ou supérieur à `a`.
*/
return (a % ALIGN_MAX == 0) ? a : a + ALIGN_MAX - (a % ALIGN_MAX);
}
static struct bloc *recherche_bloc_libre(size_t taille)
{
/*
* Recherche un bloc libre ou une suite de bloc libres dont la taille
* est au moins égale à `taille`.
*/
struct suite suite = { 0 };
struct bloc *bloc = libre;
struct bloc *precedent = NULL;
struct bloc *ret = NULL;
while (bloc != NULL)
{
if (bloc->taille >= taille)
{
if (precedent != NULL)
precedent->suivant = bloc->suivant;
else
libre = bloc->suivant;
ret = bloc;
break;
}
else if (suite.dernier != NULL && (char *)suite.dernier + TAILLE_EN_TETE \
+ suite.dernier->taille == (char *)bloc)
{
suite.dernier = bloc;
suite.taille += TAILLE_EN_TETE + bloc->taille;
}
else
{
suite.precedent = precedent;
suite.premier = bloc;
suite.dernier = bloc;
suite.taille = bloc->taille;
}
if (suite.taille >= taille)
{
if (suite.precedent != NULL)
suite.precedent->suivant = suite.dernier->suivant;
else
libre = suite.dernier->suivant;
suite.premier->taille = suite.taille;
ret = suite.premier;
break;
}
precedent = bloc;
bloc = bloc->suivant;
}
return ret;
}
static void *static_malloc(size_t taille)
{
/*
* Alloue un bloc de mémoire au moins de taille `taille`.
*/
static size_t alloue = 0UL;
void *ret;
assert(taille > 0);
taille = calcule_multiple_align_max(taille);
ret = recherche_bloc_libre(taille);
if (ret == NULL)
{
if (MEM_MAX - alloue < TAILLE_EN_TETE + taille)
{
fprintf(stderr, "Il n'y a plus assez de mémoire disponible.\n");
return NULL;
}
ret = &mem[alloue];
alloue += TAILLE_EN_TETE + taille;
bloc_init(ret, taille);
}
return (char *)ret + TAILLE_EN_TETE;
}
static void static_free(void *ptr)
{
/*
* Ajoute le bloc fourni à la liste des blocs libres.
*/
struct bloc *bloc = libre;
struct bloc *precedent = NULL;
struct bloc *nouveau;
if (ptr == NULL)
return;
nouveau = (struct bloc *)((char *)ptr - TAILLE_EN_TETE);
while (bloc != NULL)
{
if (nouveau < bloc)
{
if (precedent != NULL)
precedent->suivant = nouveau;
else
libre = nouveau;
nouveau->suivant = bloc;
break;
}
precedent = bloc;
bloc = bloc->suivant;
}
if (bloc == NULL)
libre = nouveau;
}
La fonction static_free() a été aménagée afin que les adresses des différents blocs soient triées par ordre croissant. Si le nouveau bloc libéré a une adresse inférieure à un autre bloc, il est placé avant lui, sinon il est placé à la fin de la liste.
Quant à la fonction recherche_bloc_libre(), elle emploie désormais une structure suite qui comprend un pointeur vers le bloc précédent le début de la suite (champ precedent), un pointeur vers le premier bloc de la suite (champ premier), un pointeur vers le dernier bloc de la suite (champ dernier) et la taille totale de la suite (champ taille).
Dans le cas où cette structure n’a pas encore été modifiée ou que le dernier bloc de la suite n’est pas adjacent à celui qui le suit, le premier et le dernier blocs de la suite deviennent le bloc courant, la taille est réinitialisée à la taille du bloc courant et le bloc précédent la suite est… celui qui précède le bloc courant (ou un pointeur nul s’il n’y en a pas).
Si la suite atteint une taille suffisante, alors les blocs la composant sont fusionnés et le nouveau bloc ainsi construit est retourné.
Ce chapitre clôt cette troisième partie ainsi que ce cours. N’hésitez pas à revoir l’un ou l’autre passage qui vous ont semblé difficiles ou flous avant de prendre le large vers de nouveaux horizons.