Libk : bibliothèque de fonctions standards à l'usage du système

Objectifs

Le but de cette séance est de programmer les fonctions auxiliaires et l'allocateur mémoire que va utiliser le système. Ces fonctions sont un sous-ensemble de la bibliothèque libc. La librairie contient aussi une API de gestion de listes doublement chainées que nous verrons plus tard. Nous allons écrire et valider sur Linux. Elles seront adaptées au système plus tard (il y aura très peu de modifications).

Pour les fonctions auxiliaires:

• Affichage formaté de messages pour le système
• Conversion chaine -> entier
• Déplacement de zone de mémoire
• Fonctions de manipulations des chaines
• Générateur aléatoire

Pour l'allocation dynamique:

• Allocation dynamique dans le tas du système
• libération

Principes de la gestion de la mémoire dynamique

La zone mémoire disponible pour faire des allocations dynamiques peut être vue comme un ensemble de blocs mémoires (zone de mémoire contiguë de taille variable). l'allocateur doit répondre à des requêtes de type réservation/libération de certains nombres de ces blocs.

Afin de répondre à ces requêtes, un allocateur doit connaitre l'état de ces blocs: quels sont les blocs libres et ceux occupés (pas encore libérés). Le but d'un allocateur est de répondre à ces requêtes en minimisant d'une part, l'espace mémoire perdu dû à la fragmentation des blocs et d'autre part, le temps de réponse (minimiser l'overhead de gestion).

Il existe plusieurs stratégies pour atteindre ces deux buts, mais il n'y a pas de stratégie optimale, car cela dépend du comportement du demandeur (les tailles demandées, la durée de vie d'une réservation, l'ordre des libérations, etc.).

La stratégie d'allocation que nous vous proposons d'implémenter est de type First-Fit. Dans cette stratégie, l'allocateur cherche parmi les blocs libres celui qui a une taille supérieure ou égale à la taille demandée. Il arrête sa recherche dès qu'il en trouve un. Si la taille du bloc trouvé est supérieure à la taille demandée (d'une certaine quantité), il soustrait la taille en trop et en fabrique un nouveau bloc libre. Enfin, il marque le bloc trouvé comme occupé et rend son adresse. Vous pouvez dans un second temps implémenter la stratégie Next-Fit. Dans cette stratégie, l'allocateur utilise un pointeur sur le premier bloc libre afin d'accélérer la recherche.

La figure suivante illustrent un exemple d'une allocation de 128 octets.

Lors d'une libération d'un bloc, l'allocateur essaie de fusionner (merger) les blocs libres qui suivent ce bloc (et pas ceux qui précèdent). Les figures 2 et 3 illustrent ce fusionnement de blocs en mettant en évidence la condition d'arrêt : plus de blocs libres contigus après le bloc libéré.

Nous avons vu, lors d'une allocation, que l'allocateur peut-être amené à partitionner un bloc libre si sa taille est strictement supérieure à la taille demandée.

L'allocateur doit définir une taille minimum acceptable au-dessous de laquelle le partitionnement ne se fera pas. Autrement dit si la taille restante d'un bloc libre n'est pas significative ce n'est pas la peine de partitionner ce bloc sous peine d'accroitre la fragmentation de la mémoire.

L'allocateur voit les blocs comme multiple de sous blocs de taille fixe, c'est la taille minimum pour répondre à une allocation mémoire. Par exemple : si la taille d'un bloc minimal (un sous bloc) est de 32 octets alors une allocation de 52 octets se traduit par une réservation d'un bloc de 2 * 32 soit de 64 octets. Une allocation de 4 octets se traduit par réservation d'un bloc de 1 * 32 octets. En fait, dans le but de mieux tirer profit du cache de données de niveau 1, on fixe la taille minimale d'un bloc à taille d'une ligne de cache. Dans notre cas la taille minimale sera de 64 octets (16 mots de 4 octets).

Lors de la libération, l'allocateur reçoit uniquement l'adresse du bloc à libérer, mais pas sa taille. l'allocateur doit mettre en place un mécanisme pour retrouver la taille d'un bloc à partir de son adresse.

L'allocateur associe à chaque bloc un descripteur qui indique l'état du bloc (libre ou occupé) et sa taille. Un bloc est donc composé de deux parties, un descripteur et un champ données. la figure suivante illustre cette association.

Définition des structures de données de l'allocateur

Nous allons représenter l'allocateur mémoire et la description de la zone mémoire à gérer par la structure heap_s voici sa définition en C. Le lock permet de séquencialiser les accès concurrents. Pour le test de votre API vous utiliserez un spinlock des PThreads.

struct heap_s
{
    spinlock_t lock;
    uint32_t *start;
    uint32_t *limit;
};

La structure d'un descripteur de bloc est représentée par la structure block_info_s voici sa définition en C :

struct block_info_s
{
     uint32_t busy:1;
     uint32_t size:31;
} __attribute__ ((packed));

A l'état initial, la zone mémoire est constituée d'un seul bloc libre.

L'API de notre allocateur est la suivante :

int kmalloc_init (void *start, void *limit); // rend 0 si l'initialisation est possible
void* kmalloc(size_t size);
void  kfree(void *ptr);

Travail demandé

Dans le répertoire osm1/tp1 du compte encadr, vous trouverez les 2 répertoires suivants:

|-- libk
|   |-- include
|   |-- lib
|   |-- Makefile
|   |-- obj
|   `-- src
|       |-- error.h
|       |-- katob.c
|       |-- klist.h
|       |-- kmalloc.c
|       |-- kmemmove.c
|       |-- kprintf.c
|       |-- kputs.c
|       |-- krand.c
|       |-- ksnprintf.c
|       |-- kstdio.h
|       |-- kstdlib.h
|       |-- kstrcmp.c
|       |-- kstrcpy.c
|       |-- kstrdup.c
|       |-- kstring.c
|       |-- kstrlen.c
|       |-- kvsnprintf.c
|       |-- libk.h
|       `-- linux.h
`-- test
    |-- main.c
    `-- Makefile

Pour compiler vous devez

• aller dans le répertoire libk et taper make.
• aller dans le répertoire test et taper make

Pour chaque fonction, ou groupe de fonction (kmalloc), vous allez devoir écrire le service et le programme de test en faisant attention à tester les cas limites. Les fichiers sont compilables, mais sont vides ou appelle le service de la libc de linux. Je vous demande aussi de commenter en détail les Makefile.

Vous pouvez créer des fichiers de test par service.

• ./test_kstrlen
• ./tsst_kmalloc

Pour le kmalloc votre application de test doit déclarer un tableau d'octets représentant la mémoire à gérer par le heap_manager.

#define ZONE_SIZE      8*1024
int8_t zone [ZONE_SIZE];

Vous pourrez écrire une fonction kmalloc_status qui affiche l'état des blocs de l'allocateur.

void kmalloc_status(void);

Rapport

Je vous demande un rapport sur les fonctions de cette librairie (comment on les utilise et comment elles marchent) et sur les tests que vous avez mis en oeuvre. Je vous demande aussi de commenter le Makefile.