CSC 4103 – Programmation système

Portail informatique

Le devoir est à rendre sur moodle le 14/2/2020 à 23h55 au plus tard

Cet exercice a pour but de vous familiariser avec les structures algorithmiques de base et les structures de données en langage C.

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.

Lors de la soumission de ce devoir, tâchez de rendre un code propre et compréhensible (indentation correcte, noms de variables expressives, etc.) Un malus pourra être appliqué à votre note si ce n'est pas le cas ! L'objectif de cet exercice est de développer les fonctionnalités "de base" de l'allocateur mémoire.

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.

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.

Le fichier memory_alloc.c contient un ensemble tests unitaires permettant de tester le code développé pour les exercices 1 et 2. Ces tests ne sont bien sûr pas exhaustifs. N'hésitez pas à les modifier pour effectuer des tests plus poussés que ceux proposés.

Le système de tests unitaires repose sur cmocka. Pour compiler le programme, utilisez la ligne de commande suivante:

gcc memory_alloc.c -o memory_alloc -g -O0 -Wall -L. -lm -lcmocka

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 :

$ ./install_cmocka.sh [...] installation du fichier libcmocka.a... OK ! installation du fichier cmocka.h... OK !

La compilation devrait alors se passer sans erreur.

Une fois le programme memory_alloc compilé, vous pouvez l'exécuter. Puisque vous n'avez pas encore implémenté certaines fonctions, aucun des tests ne réussi:

$ ./memory_alloc [==========] Running 9 test(s). [ RUN ] test_exo1_memory_init [ ERROR ] --- 0 != 0x10 [ LINE ] --- memory_alloc.c:108: error: Failure! [ FAILED ] test_exo1_memory_init [ RUN ] test_exo1_memory_print [ ERROR ] --- 0 != 0x10 [ LINE ] --- memory_alloc.c:108: error: Failure! [ FAILED ] test_exo1_memory_print [ RUN ] test_exo1_alloc_one_byte [ ERROR ] --- 0 != 0x10 [ LINE ] --- memory_alloc.c:108: error: Failure! [ FAILED ] test_exo1_alloc_one_byte [ RUN ] test_exo1_alloc_one_page [ ERROR ] --- 0 != 0x10 [ LINE ] --- memory_alloc.c:108: error: Failure! [ FAILED ] test_exo1_alloc_one_page [ RUN ] test_exo1_alloc_two_pages [ ERROR ] --- 0 != 0x10 [ LINE ] --- memory_alloc.c:108: error: Failure! [ FAILED ] test_exo1_alloc_two_pages [ RUN ] test_exo1_free_blocks [ ERROR ] --- 0 != 0x10 [ LINE ] --- memory_alloc.c:108: error: Failure! [ FAILED ] test_exo1_free_blocks [ RUN ] test_exo1_multiple_alloc [ ERROR ] --- 0 != 0x10 [ LINE ] --- memory_alloc.c:108: error: Failure! [ FAILED ] test_exo1_multiple_alloc [ RUN ] test_exo1_out_of_memory [ ERROR ] --- 0 != 0x10 [ LINE ] --- memory_alloc.c:108: error: Failure! [ FAILED ] test_exo1_out_of_memory [ RUN ] test_exo2_reorder [ ERROR ] --- 0 != 0x10 [ LINE ] --- memory_alloc.c:108: error: Failure! [ FAILED ] test_exo2_reorder [==========] 9 test(s) run. [ PASSED ] 0 test(s). [ FAILED ] 9 test(s), listed below: [ FAILED ] test_exo1_memory_init [ FAILED ] test_exo1_memory_print [ FAILED ] test_exo1_alloc_one_byte [ FAILED ] test_exo1_alloc_one_page [ FAILED ] test_exo1_alloc_two_pages [ FAILED ] test_exo1_free_blocks [ FAILED ] test_exo1_multiple_alloc [ FAILED ] test_exo1_out_of_memory [ FAILED ] test_exo2_reorder 9 FAILED TEST(S)
Implémentez la fonction void memory_init(). Cette fonction est chargée d'initialiser tous les champs de la structure m. Une fois la fonction implémentée, le premier test devrait fonctionner: $ ./memory_alloc [==========] Running 9 test(s). [ RUN ] test_exo1_memory_init [ OK ] test_exo1_memory_init [ RUN ] test_exo1_memory_print --------------------------------- Block size: 8 Available blocks: 16 First free: 0 Status: Success Content: --------------------------------- [ OK ] test_exo1_memory_print [ RUN ] test_exo1_alloc_one_byte [ ERROR ] --- 0xffffffffffffffff == 0xffffffffffffffff [ LINE ] --- memory_alloc.c:100: error: Failure! [ FAILED ] test_exo1_alloc_one_byte [ RUN ] test_exo1_alloc_one_page [ ERROR ] --- 0xffffffffffffffff == 0xffffffffffffffff [ LINE ] --- memory_alloc.c:100: error: Failure! [...]

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 :

La fonction devrait afficher:

Block size: 8 Available blocks: 4 First free: 1 Status: Success Content: [1] -> [2] -> [3] -> [6] -> NULL_BLOCK

Une fois la fonction complétée, le programme devrait afficher:

$ ./memory_alloc [==========] Running 9 test(s). [ RUN ] test_exo1_memory_init [ OK ] test_exo1_memory_init [ RUN ] test_exo1_memory_print --------------------------------- Block size: 8 Available blocks: 16 First free: 0 Status: Success Content: [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] -> [10] -> [11] -> [12] -> [13] -> [14] -> [15] -> NULL_BLOCK --------------------------------- [ OK ] test_exo1_memory_print [ RUN ] test_exo1_alloc_one_byte [ ERROR ] --- 0xffffffffffffffff == 0xffffffffffffffff [ LINE ] --- memory_alloc.c:108: error: Failure! [ FAILED ] test_exo1_alloc_one_byte [ RUN ] test_exo1_alloc_one_page [ ERROR ] --- 0xffffffffffffffff == 0xffffffffffffffff [...]

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 :

--------------------------------- Block size: 8 Available blocks: 4 First free: 4 Status: Success Content: [4] -> [12] -> [13] -> [14] -> NULL_BLOCK --------------------------------- nb_consecutive_blocks(12) returned 3

Implémentez la fonction int memory_allocate(size_t size). Cette fonction 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 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 position m.error_no à E_NOMEM.

Utilisez ensuite le programme de test pour tester votre implémentation. Les tests proposés ne sont pas exhaustifs et peuvent bien sûr être complétés. Voici un exemple d'exécution attendue:

$ ./memory_alloc [==========] Running 9 test(s). [ RUN ] test_exo1_memory_init [ OK ] test_exo1_memory_init [ RUN ] test_exo1_memory_print --------------------------------- Block size: 8 Available blocks: 16 First free: 0 Status: Success Content: [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] -> [10] -> [11] -> [12] -> [13] -> [14] -> [15] -> NULL_BLOCK --------------------------------- [ OK ] test_exo1_memory_print [ RUN ] test_exo1_alloc_one_byte [ OK ] test_exo1_alloc_one_byte [ RUN ] test_exo1_alloc_one_page [ OK ] test_exo1_alloc_one_page [ RUN ] test_exo1_alloc_two_pages [ OK ] test_exo1_alloc_two_pages [ RUN ] test_exo1_free_blocks [ ERROR ] --- 0xc != 0x10 [ LINE ] --- memory_alloc.c:228: error: Failure! [ FAILED ] test_exo1_free_blocks [...]

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 à la liste des blocs disponibles.

Pour cette question, veillez à implémenter un algorithme s'exécutant en temps constant (ie. de complexité O(1)) car:

  • la fonction memory_free risque d'être appelée fréquemment. Il est donc importat 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 cette allouée).

Voici un exemple d'exécution attendue:

$ ./memory_alloc [ RUN ] test_exo1_memory_init [ OK ] test_exo1_memory_init [ RUN ] test_exo1_memory_print --------------------------------- Block size: 8 Available blocks: 16 First free: 0 Status: Success Content: [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] -> [10] -> [11] -> [12] -> [13] -> [14] -> [15] -> NULL_BLOCK --------------------------------- [ OK ] test_exo1_memory_print [ RUN ] test_exo1_alloc_one_byte [ OK ] test_exo1_alloc_one_byte [ RUN ] test_exo1_alloc_one_page [ OK ] test_exo1_alloc_one_page [ RUN ] test_exo1_alloc_two_pages [ OK ] test_exo1_alloc_two_pages [ RUN ] test_exo1_free_blocks [ OK ] test_exo1_free_blocks [ RUN ] test_exo1_multiple_alloc [ OK ] test_exo1_multiple_alloc [ RUN ] test_exo1_out_of_memory [ OK ] test_exo1_out_of_memory [ RUN ] test_exo2_reorder [ ERROR ] --- 0x2 != 0 [ LINE ] --- memory_alloc.c:341: error: Failure! [ FAILED ] test_exo2_reorder [==========] 9 test(s) run. [ PASSED ] 8 test(s). [ FAILED ] 1 test(s), listed below: [ FAILED ] test_exo2_reorder 1 FAILED TEST(S)
L'objectif de cet exercice est d'améliorer l'allocateur mémoire afin de le rendre plus robuste.

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):

Pour illustrer le problème, examinez la fonction test_exo2. Il est probable que votre programme affiche:

[...] [ RUN ] test_exo2_reorder --------------------------------- Block size: 8 Available blocks: 16 First free: 15 Status: Success Content: [15] -> [13] -> [11] -> [9] -> [7] -> [5] -> [3] -> [1] -> [14] -> [12] -> [10] -> [8] -> [6] -> [4] -> [2] -> [0] -> NULL_BLOCK --------------------------------- [ ERROR ] --- 0x2 != 0 [ LINE ] --- memory_alloc.c:341: error: Failure! [ FAILED ] test_exo2_reorder [...]

Ici, on observe que 16 blocs mémoires sont disponibles, mais qu'ils sont "mélangés". Il est donc impossible d'allouer 2 blocs mémoires consécutifs. Dit autrement, nb_consecutive_blocks(0) considère, à raison, qu'il n'y a qu'un bloc contigu disponible à partir du bloc d'indice 0, alors qu'idéalement, il devrait en trouver 16."

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).

Lors de l'implémentation de cette fonction, veillez à effectuer le tri à bulle directement sur la liste des blocs sans allouer de tableau supplémentaire.

Modifiez la fonction memory_allocate afin qu'elle appellememory_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.

Les fonctions test_exo1 et test_exo2 devraient maintenant s'exécuter correctement!