1  Allocateur de blocs de taille fixe – atf

Notre premier allocateur va être capable d’allouer et de libérer des blocs mémoire d’une taille fixe donnée.

1.1  Interface de notre allocateur de taille fixe

L’interface de cet allocateur définit la constante

#define ATF_BLOCSIZE    ...

qui précise la taille des blocs.

Il est possible de demander l’allocation d’un bloc par un appel à

void * atf_newbloc(); 

qui retourne l’adresse d’un bloc mémoire de ATF_BLOCSIZE octets. Cette fonction atf_newbloc() retourne NULL en cas d’erreur, c’est-à-dire si il n’y a plus de mémoire disponible.

Un bloc précédement alloué peut être libéré par un appel à

int atf_freebloc(void *bloc);

qui retourne 0 en seul cas de succès.

L’allocateur offre aussi une fonction atf_init() d’initialisation qui devra être appelée une et une unique fois avant l’utilisation des autres primitives.

1.2  Implémentation de notre allocateur de taille fixe

Une première implémentation consiste à utiliser un tableau alloué statiquement pour y garder les blocs.

On définit le nombre de blocs pouvant être alloués et déclare ce tableau :

#define NBLOCS   ...
static char membloc[NBLOCS][ATF_BLOCSIZE];

Il s’agit ensuite de pouvoir identifier parmi les NBLOCS ceux qui sont libres.

On utilise un autre tableau

static char memstatus[NBLOCS];

qui pour chaque bloc indique s’il est libre (0) ou non (une valeur non nulle).

L’allocation d’un bloc consiste donc à rechercher une valeur nulle dans le tableau memstatus.

La libération d’un bloc consiste à retrouver le numéro du bloc à partir de l’adresse passée en paramètre et à marquer le bloc comme libre.

1.3  Validation à minima de notre allocateur de taille fixe

Une première validation a minima de notre bibliothèque peut consister en un programme qui

• alloue des blocs tant que possible via des appels à atf_newbloc() ;
• tout en mémorisant les adresses retournées certains de ces appels à atf_newbloc(), disons 42 adresses ;
• libère les blocs correspondant à ces 42 adresses ;
• alloue des blocs tant que possible ;
• vérifie que cela a permis d’allouer exactement 42 blocs ;
• vérifie que les adresses de ces 42 blocs correspondent exactement à celles des blocs libérés.

1.4  Test par le jeu de la lettre qui saute

Vous trouverez dans le dépôt

https://gitlab-etu.fil.univ-lille1.fr/ls4-pdc/validation_atf

• un exécutable jeu (elf linux) ;
• un dictionnaire de mots de 4 lettres (dico4lettres.h) ;
• un Makefile ;
• les fichiers sources jeu.c (similaire à ce qui a été vu en cours) et gestionpile.c (similaire à ce qui va être vu en td).

Le jeu consiste à se donner deux mots dans un dictionnaire (dico4lettres.h) et à voir s’il est possible de passer de l’un à l’autre en respectant la règle suivante : on passe d’un mot à un autre par une suite de mots ne diffèrant que d’une lettre. Par exemple, on peut passer de lion à peur par la suite de mots :

lion -> pion -> paon -> pain -> paix -> poix -> poux -> pour -> peur

Pour tester le programme jeu, vous pouvez passer de doux à dure. Ceci fait, effacez l’exécutable jeu.

1.5  Implémentation alternative de notre allocateur de taille fixe

En comparant la taille des tableaux membloc et memstatus, nous pouvons questionner le coût mémoire de cet allocateur et proposer une alternative.

Chaque valeur du tableau memstatus pourrait être mémorisée sur un bit, nous pourrions enregister 8 valeurs par octets, et ainsi déclarer (en supposant NBLOCS multiple de 8) :

static char memstatus_b[NBLOCS/8];

Nous pourrions aussi imaginer déclarer un tableau

enum memstatus_e {MEM_FREE=0, MEM_USED};
static enum memstatus_e memstatus_s[NBLOCS];