Devoir hors présentiel
L'exercice consiste à développer un allocateur mémoire 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(size_t n_bytes); Cette fonction retourne l'adresse (l'indice de début dans un tableau) d'une zone mémoire de n_bytes octets.
- void memory_free(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 un tableau de N blocs. Pour l'exercice, on considèrera que chaque bloc fait 64 bits (8 octets). 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'indice 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 64 bits (8 octets). Les blocs libres forment une liste chaînée: chaque bloc contient l'indice 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 (notez que, pour ce devoir, vous n'aurez besoin que de modifier memory_alloc.c ; toutefois, si vous estimez avoir quand même besoin de modifier memory_alloc.h, veuillez préalablement contacter l'équipe pédagogique de CSC4103 pour en discuter et potentiellement améliorer memory_alloc.h).
Tout au long de ce devoir hors présentiel, 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 memory_alloc.c, un ensemble de tests pour tester le code développé pour les exercices 1 et 2. Pour l'instant, vu que vous n'avez écrit aucun code, ces tests sont bien évidemment tous en ERROR. L'idée est qu'au fur et à mesure de votre avancement dans ce devoir, ils passent à OK. Si vous le souhaitez, n'hésitez pas à en ajouter pour aller plus loin que les tests déjà fournis.
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 memory_alloc compilé, vous pouvez l'exécuter. Puisque vous n'avez encore rien implémenté, aucun des tests ne réussit:
Remarquez comment, lorsqu'un test échoue, cmocka indique le numéro de ligne où a lieu l'erreur. Par exemple:
- La deuxième ligne de l'affichage ([ RUN ] test_exo1_memory_init) et la troisième ligne ([ ERROR ] --- 0x7fffffff != 0) indiquent que, lors de l'exécution du test test_exo1_memory_init, une erreur a été observée car la valeur obtenue a été 0x7fffffff alors que la valeur attendue était 0
- Cette erreur est advenue à la ligne 115 du fichier memory_alloc.c (cf. 4ème ligne de l'affichage [ LINE ] --- memory_alloc.c:115: error: Failure!).
Regardez cette ligne 115 du fichier memory_alloc.c et les lignes autour:
Ce test de la ligne 115 révèle qu'il manque actuellement, dans memory_init(), au moins une instruction qui positionne m.first_block à 0 (cf. la question suivante).
Avant de passer à la question suivante, quelques remarques liées au fonctionnement de cmoka:
- Cmocka affiche les entiers en hexadécimal :
- Par exemple, 0xf correspond au nombre 15 exprimé en hexadécimal, vu que le chiffre "f" a pour valeur 15 en hexadécimal.
- 0x7fffffff correspond à la constante NULL_BLOCK.
- 0xffffffffffffffff correspond à la constante INT32_MIN (redéfinie en A_B dans memory_alloc.c) utilisée pour remplir des blocs alloués à l'utilisateur.
- Durant votre travail d'implémentation, il se peut que cmocka vous affiche
Test failed with exception: Segmentation fault(11) comme résultat de test. Par exemple :
Cela signifie que la fonction que cmocka est en train de tester fait un accès mémoire illicite. Dans l'exemple ci-dessus, cmocka a appelé la fonction test_exo1_nb_consecutive_blocks_at_beginning_linked_list() qui, si vous consultez son code dans memory_alloc.c, contient l'instruction assert_int_equal(nb_consecutive_blocks(8), 2); qui appelle la fonction nb_consecutive_blocks(). C'est cette dernière qui fait un accès mémoire illicite.$ ./memory_alloc [==========] Running 11 test(s). [ RUN ] test_exo1_memory_init [ OK ] test_exo1_memory_init [ RUN ] test_exo1_nb_consecutive_blocks_at_beginning_linked_list [ ERROR ] --- Test failed with exception: Segmentation fault(11) [ FAILED ] test_exo1_nb_consecutive_blocks_at_beginning_linked_list ... [==========] 11 test(s) run. ... [ FAILED ] test_exo2_memory_reorder_leading_to_failed_memory_allocate
Dans ces exercices, il est probable que votre code fasse une instruction du style m.blocks[index] = val; et que la variable index contienne la valeur NULL_BLOCK ou A_B.
Corrigez le problème, recompilez et relancez votre programme.
NB: Si vous ne voyez vraiment pas pourquoi vous avez un accès mémoire illicite, exécutez votre programme sous débugger (cf. séance dédiée de CSC4103). - Durant votre travail d'implémentation, il se peut aussi que cmocka s'arrête en plein milieu d'un test. Par exemple :
Cela signifie que la fonction que cmocka est en train de tester fait une boucle infinie. Dans l'exemple ci-dessus, cmocka a appelé la fonction test_exo1_nb_consecutive_blocks_at_beginning_linked_list() qui, si vous consultez son code dans memory_alloc.c, contient l'instruction assert_int_equal(nb_consecutive_blocks(8), 2); qui appelle la fonction nb_consecutive_blocks(). C'est cette dernière qui fait une boucle infinie et ne rend donc jamais la main à test_exo1_nb_consecutive_blocks_at_beginning_linked_list().$ ./memory_alloc [==========] Running 11 test(s). [ RUN ] test_exo1_memory_init [ OK ] test_exo1_memory_init [ RUN ] test_exo1_nb_consecutive_blocks_at_beginning_linked_list Et pas d'autre affichage, ni de prompt Unix !
Appuyez sur "Ctrl-C" pour arrêter votre programme, corrigez le problème, recompilez et relancez votre programme.
Implémentez la fonction void memory_init(). Cette fonction est chargée d'initialiser tous les champs de la structure m. Le tableau blocks devrait contenir:
Une fois la fonction implémentée, le premier test devrait fonctionner:
Complétez maintenant la fonction memory_print pour qu'elle affiche la liste des blocs disponibles. Par exemple, si l'état du tableau des blocs mémoires est :
Pour Error_no, affichez la valeur du champs m.error_np. Si cette valeur ne fait partie de l'enum memory_errno, affichez Unknown. Ce code d'erreur est utilisé dans les fonctions memory_allocate et memory_free.
La fonction devrait afficher:
Pour tester que votre implémentation de memory_print() est correcte, modifiez le code du test test_exo1_nb_consecutive_blocks_at_beginning_linked_list() de la manière suivante :
A l'exécution, vous devriez obtenir l'affichage :
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.
Implémentez la fonction int nb_consecutive_blocks(int 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 int memory_allocate(size_t size). Cette fonction parcourt la liste chaînée et cherche une suite de blocs consécutifs libre 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 initialize_buffer(start_index, size) qui remplit la zone de zéros), et retourne l'indice du premier bloc de la suite.
S'il n'y a pas suffisament de blocs disponibles pour stocker size octets, la fonction retourne -1 et positionne m.error_no à E_NOMEM.
Implémentez la fonction void memory_free(int address, size_t size). Cette fonction "désalloue" la zone de size octets débutant à l'indice 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 memory_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 devoir, cela assure qu'un problème aura bien lieu au début de l'exercice 2 :-)
NB: pour cette fonction, on considère que la zone à libérer a été allouée avec memory_alloc 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):
Créez une fonction void memory_reorder() 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 memory_allocate afin qu'elle appelle memory_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 memory_allocate, si après l'appel à memory_reorder il n'y a toujours pas N blocs consécutifs (où N est le nombre de blocs à allouer), la fonction retourne -1 et positionne m.error_no à E_SHOULD_PACK.
