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 systeme. Ces fonctions sont un sous-ensemble de la bibliothèque libc.

Nous allons les écrire et les valider sur Linux. Elles seront adaptées au système plus tard.

Pour les fonctions auxiliaires:

• kprintf : Affichage formaté de messages pour le système
• kgetc, kgets : Lecture d'un caractère ou d'une ligne (jusqu'au return)
• strtol : Conversion chaine -> entier
• memcpy : Déplacement de zone de mémoire
• strcmp : Fonctions de manipulations des chaines
• rand : Un générateur aléatoire
• list : Gestion de listes chainées

Pour l'allocation dynamique:

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

Gestion de la mémoire dynamique

Principes

L'allocation dynamique de la mémoire est une fonctionnalité fondamentale qui fait partie des systèmes d'exploitation depuis les années 1960.

La zone mémoire disponible pour faire des allocations dynamiques peut être vue comme un ensemble de blocs mémoire (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 mené à partitionner un bloc libre si sa taille est strictement supérieur à la taille demandée de certaine quantité. Le choix de cette quantité est très important pour la réutilisation des blocs.

L'allocateur doit définir une taille minimum acceptable au dessous du 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

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é

Le travail à réaliser est d'implémenter cette API et la tester par une application de test.

Votre application de teste doit déclarer deux variables globales, une de type heap_s et l'autre est 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];
struct heap_s heap;

Vous devez donc écrire les trois fonctions de l'API dans le fichier kmalloc.c et leur prototype dans le fichier kmalloc.h. En cas d'échec du malloc, vous devrez faire un parcours de la zone mémoire et fusionner les zones libres contiguës.

Vous écrirez un programme de test dans le fichier main.c mettant en évidence les cas de fonctionnement.

Afin de mettre au point votre allocateur, il est utile d'écrire une fonction qui affiche l'état des blocs de l'allocateur, par exemple

void kmalloc_print(void);