Projet: allocateur mémoire
L'exercice consiste à développer un arena memory allocator permettant d'allouer dynamiquement de la mémoire. Le but d'un allocateur mémoire est de fournir deux primitives à une application:
- int memory_allocate(struct memory_alloc* m, size_t n_bytes); Cette fonction retourne l'adresse d'une zone mémoire de n_bytes octets.
- void memory_free(struct memory_alloc* m, int address, size_t n_bytes); Cette fonction libère la zone mémoire de n_bytes situées à l'adresse address.
Pour cela, l'allocateur mémoire crée une liste chaînée de N blocs. Lorsque l'application demande l'allocation de size octets, l'allocateur cherche une suite de blocs consécutifs suffisament longue pour stocker size octets, et retourne l'adresse du premier bloc de cette suite. Lorsque l'application libère une zone mémoire, l'allocateur ajoute les blocs libérés à la liste des blocs disponibles.
Memory allocator
L'allocateur mémoire que nous allons concevoir repose sur un tableau de blocs mémoires. Chaque bloc mémoire fait block_size octets. Les blocs libres forment une liste chaînée: chaque bloc contient l'adresse du prochain bloc libre.
Voici un exemple d'état du tableau des blocs mémoires:
Dans cet exemple, le premier bloc libre est à l'indice 1. La valeur stockée dans la case 1 correspond à l'indice du bloc suivant, ici 2. A la fin de la liste chainée, (ici, dans la case d'indice 6), la valeur NULL_BLOCK indique qu'il n'y a pas de bloc suivant. Ici, X représente une valeur quelconque choisie par l'application.
Dans cet exemple, la fonction memory_print() devrait afficher:
Si l'application fait l'appel memory_allocate(14), l'allocateur mémoire cherchera 2 blocs (permettant de stocker jusqu'à 16 octets) consécutifs libres. Par exemple :
Ici, l'allocateur choisit les deux premiers blocs (d'indice 1 et 2). La liste des blocs libres est donc modifiée pour supprimer ces deux blocs. La valeur retournée par memory_allocate correspond à l'indice du premier bloc alloué: 1.
Si l'application fait l'appel memory_free(4, 13), pour libérer la zone de 13 octets débutant à l'indice 4, l'allocateur mémoire ajoutera les 2 blocs (permettant de stocker jusqu'à 16 octets) à la liste des blocs libres. Par exemple :
Ici, les deux blocs libérés (d'indice 4 et 5) sont ajoutés au début de la liste des blocs disponibles.
Téléchargez l'archive sujet.tgz, extrayez la et étudiez les fichiers memory_alloc.h et memory_alloc.c.
Tout au long de ce projet, nous vous proposons d'adopter la méthode de développement Test-Driven Development (TDD), ou développement piloté par les tests en français. Nous vous fournissons, dans le fichier test_memory_alloc.c, un ensemble de tests pour tester le code du projet. Cet ensemble de test est pour l'instant très sommaire, et il vous est demander de la compléter tout au long du projet afin de vous assurer que les fonctionnalités que vous développez sont exemptes de bug.
Le système de tests unitaires repose sur cmocka. Pour compiler le programme, utilisez la ligne de commande suivante:
Si cette ligne de compilation ne fonctionne pas, c'est sans doute parce que vous êtes dans un environnement particulier (machine Mac Os, ou processeur autre que x86_64 par exemple) qui fait que le fichier libcmocka.a est inutilisable. Pour en créer un qui soit utilisable, exécutez le script install_cmocka.sh :
La compilation devrait alors se passer sans erreur.
Une fois le programme test_memory_alloc compilé, on observe que les tests ne fonctionnent pas (puisque vous n'avez pas encore implémenté ces fonctionnalités). Remarquez comment, lorsqu'un test échoue, cmocka indique le numéro de ligne où a lieu l'erreur.
Pendant ce projet, il vous est demandé de compléter la liste des tests afin de vérifier le bon fonctionnement du code développé. Pour ajouter un test, définissez une fonction void nom_du_test(void** state), et ajoutez la à la liste des tests à exécuter (dans la fonction main). Votre fonction nom_du_test doit ensuite appeler votre code, et vérifier son bon fonctionnement à l'aide d'assertions. La liste des assertions possible dans cmocka est disponible ici.
Implémentez la fonction void memalloc_init(struct memory_alloc* m, int nb_blocks, size_t block_size). Cette fonction est chargée d'initialiser tous les champs de la structure m et de préallouer nb_blocks de taille block_size. Le tableau blocks devrait contenir:
Implémentez la fonction void memalloc_finalize(struct memory_alloc* m). Cette fonction doit libérer la mémoire allouée par memalloc_init et remettre à zéro les différents champs de la structure m.
Une fois la fonction implémentée, le premier test devrait fonctionner:
Complétez maintenant la fonction memalloc_print pour qu'elle affiche la liste des blocs disponibles. Par exemple, si l'état du tableau des blocs mémoires est :
Pour afficher errno, vous pouvez utiliser la fonction memalloc_error_print.
Le programme memory_alloc devrait afficher:
Pour allouer une zone mémoire, nous allons avoir besoin de calculer la taille d'une zone mémoire libre. Cette taille correspond au nombre de blocs libres dans des cases successives du tableau prealloc_blocks.
Implémentez la fonction int memalloc_nb_consecutive_blocks(struct memory_alloc* m, struct memory_block* first). Cette fonction compte le nombre de blocs "consécutifs" (c'est à dire placés dans des cases consécutives du tableau) à partir du bloc first.
Voici un exemple d'utilisation de cette fonction :
Implémentez la fonction void* memalloc_allocate(struct memory_alloc* m, size_t size). Cette fonction parcourt la liste chaînée et cherche une suite de blocs consécutifs libres permettant de stocker size octets. Lorsqu'une telle suite de blocs est trouvée, la fonction met à jour la liste des blocs disponibles, initialise la zone mémoire (en appelant void initialize_buffer(struct memory_block* block, size_t size) qui remplit la zone de zéros), et retourne l'adresse du premier bloc de la suite.
S'il n'y a pas suffisamment de blocs disponibles pour stocker size octets, la fonction retourne NULL et positionne m.errno à E_NOMEM.
Implémentez la fonction void memalloc_free(struct memory_alloc* m, void* address, size_t size). Cette fonction "désalloue" la zone de size octets débutant à l'adresse address du tableau. La "désallocation" consiste à ajouter les blocs de la zone à libérer au début de la liste des blocs disponibles.
Pour cette question, veillez à implémenter un algorithme s'exécutant avec une complexité O(N) (où N est le nombre de blocs que la fonction libère) car:
- la fonction memalloc_free risque d'être appelée fréquemment. Il est donc important qu'elle s'exécute le plus rapidement possible
- dans le cadre de ce projet, cela assure qu'un problème aura bien lieu au début de l'exercice suivant :-)
NB: pour cette fonction, on considère que la zone à libérer a été allouée avec memalloc_allocate et que l'utilisateur ne s'est pas "trompé" (en déallouant une zone plus petite/grande que celle allouée).
Défragmentation
L'implémentation que vous avez faite lors de l'exercice 1 souffre (très probablement) de problèmes qui apparaissent au fur et à mesure des allocations/désallocations. Un des problèmes susceptibles d'apparaître est dû à la façon de libérer la mémoire: les blocs libérés sont ajoutés au début de la liste des blocs disponibles. Cela peut conduire à la situation suivante:
A partir de cet état de la mémoire
On libère, la zone de 2 blocs mémoire commençant à l'indice 4:
Il en résulte que 4 blocs sont disponibles. Toutefois, si l'application demande l'allocation d'une zone de 4 blocs, le parcours de la liste (indice 4, puis 5, puis 3, puis 6) fait apparaître qu'il n'y a pas 4 blocs consécutifs.
Une solution serait, dans ce type de situation, de réordonner la liste de blocs de sorte que le suivant j de chaque bloc libre i ait un indice plus grand (ie. i < j):
Implémentez la fonction void memalloc_reorder(struct memory_alloc* m) chargée de trier les éléments de la liste de blocs disponibles selon leur indice. Cette fonction doit implémenter un tri à bulle (une autre explication est disponible en vidéo ici).
Modifiez la fonction memalloc_allocate afin qu'elle appelle memalloc_reorder lorsqu'il n'y a plus assez de blocs consécutifs pour maximiser les chances de satisfaire une demande d'allocation mémoire de taille importante.
Dans la fonction memalloc_allocate, si après l'appel à memalloc_reorder il n'y a toujours pas N blocs consécutifs (où N est le nombre de blocs à allouer), la fonction retourne NULL et positionne m.errno à E_SHOULD_PACK.
Pour aller plus loin: fonctions d'allocation plus conformes aux fonctions du langage C
Implémentez les fonctions memalloc_lifelike_malloc(), memalloc_lifelike_free() et memalloc_lifelike_realloc(). NB :
- Conformez-vous aux spécifications rédigées dans memory_alloc.h. Pour information, ces spécifications sont un copier-coller du man des fonctions malloc, free et realloc.
-
memalloc_lifelike_free() (respectivement memalloc_lifelike_realloc()) n'a pas
de paramètre indiquant la taille de la zone mémoire qui doit être libérée (respectivement réallouée).
Pour lui permettre de retrouver cette taille, la technique suivante est mise en place :
- Le code de memalloc_lifelike_malloc() alloue sizeof(void*) octets de plus que nécessaire, afin de
stocker la taille de la zone allouée buffer_size au début du buffer. L'adresse renvoyée par memalloc_lifelike_malloc est alors
l'adresse de la zone mémoire immédiatement après buffer_size.
Par exemple, supposons qu'on appelle memalloc_lifelike_malloc(m, 9) (avec m initialisé avec une taille de bloc de 8). Logiquement, il faut seulement 2 blocs de 8 octets pour répondre à cette demande d'allocation de 9 octets. Mais, memalloc_lifelike_malloc() va allouer 8 octets supplémentaires pour mémoriser la taille dans le premier de ces 3 blocs. Concrètement, si on imagine que memalloc_lifelike_malloc() constate que les blocs 10 (adresse 0x1010), 11 (adresse 0x1018) et 12 (adresse 0x1020) sont disponibles, alors, dans le bloc 10, il stocke la valeur 24 (correspondant à la taille des 3 blocs qu'il a récupérés). Puis, il retourne l'adresse 0x1018 (et non 0x1010, vu que le bloc 10 sert de zone de stockage pour la longueur de la zone allouée). - Ainsi, quand memalloc_lifelike_free() reçoit le champ addr contenant
l'adresse à libérer, il libère l'adresse addr - sizeof(void*) en indiquant la longeur trouvée
en addr - sizeof(void*).
Reprenons l'exemple précédent : supposons qu'on appelle memalloc_lifelike_free(0x1018). memory_lifelike_free() lit à l'adresse 0x1018 - 8 = 0x1010 qu'il y a 24 octets. Il doit donc libérer 24 octets à partir de l'adresse 0x1010 - Même principe pour memory_lifelike_realloc().
- Le code de memalloc_lifelike_malloc() alloue sizeof(void*) octets de plus que nécessaire, afin de
stocker la taille de la zone allouée buffer_size au début du buffer. L'adresse renvoyée par memalloc_lifelike_malloc est alors
l'adresse de la zone mémoire immédiatement après buffer_size.
Pour aller (encore) plus loin
- Vous assurer que les adresses retournées par memalloc_lifelike_malloc sont des multiples de 16. En effet, certaines instructions (notamment des instructions vectorielles) nécessitent des adresses alignées.
- Détecter, lors de l'appel à memalloc_lifelike_free si un débordement de tampon a eu lieu. Pour cela, placez lors de memalloc_lifelike_malloc un canari (une valeur spéciale, par exemple 0xdeadbeef) juste avant et/ou après la zone mémoire allouée. Lors de l'appel à memalloc_lifelike_free (ou à realloc), vérifiez que le canari n'a pas changé.
