Composant storage

Introduction

Un problème tant classique que recurrent se pose très souvent. C'est le problème de la gestion de la mémoire. En temps normal, pour de petites quantités de mémoire ponctuellement nécessaires, les points d'entrée malloc() et free() remplissent très bien leur fonction. Cependant, lorsqu'il est nécessaire d'allouer de grandes quantités de mémoire dont tous les atomes sont équivalent en taille, ces fonctions standards laissent à désirer, en particulier du fait de leur faibles performances et du nombre d'appels importants à ces routines.
Une autre fonction standard est calloc(), peut nous aider lorsque l'on gère des tableaux. Malgré tout, cette fonction ne permet pas de modifier la taille des tableaux alloués. Il est alors nécessaire de passer par realloc() sans garantie que les données existantes ne seront pas déplacées.
Le composant « storage » nous permet de simplifer la gestion de la mémoire pour des tableaux de grandes tailles, dont tous les composants sont équivalents. Il nous permet d'ajouter autant d'éléments que l'on veut, s'occupe de réallouer si besoin, garantit que les données ne seront pas déplacées lors des acroissements de taille. Il ne permet pas, par contre de déallouer des éléments de manière atomique. En revanche, l'opération de libération de la mémoire, lors de la désallocation, s'effectuera très rapidement.
Ce composant sera particulièrement utile lors de la mise en cache non destructif de données en mémoire, ou encore lors de l'allocation de nombreux sous-éléments équivalents d'une seule et même entité.

Principe

Le principe du composant storage repose sur celui des tableaux dynamiques. Connaissant la taille d'un élément, le composant pré-alloue une certaine quantité d'éléments.
Lorsqu'un nouvel espace est demandé, le pointeur sur les données locales est passé à la fonction. La fonction prend le premier espace libre du tableau et recopie les données du pointeur sur la variable locale de la fonction appelante, puis le « nouveau » pointeur est retourné.
S'il n'y a plus d'espace disponible, le composant réalloue la même quantité qu'il avait préallouée au départ. Cette quantité représente la « granularité » de l'allocation. Elle est passée en paramètre avec la taille d'un élément lors de la construction du composant.
La réallocation ne peut pas s'effectuer de manière directe par un simple realloc(). En effet, la fonction de réllocation de la bibliothèque standard ne garantie pas la pérénité de la position dans la mémoire. Au contraire, realloc() se charge même de déplacer les données (de les recopier) dans la nouvelle zone mémoire si la précédente ne permettait pas le redimentionnement.
Cette pratique est la plupart du temps tout à fait raisonnable. Mais dans notre cas de figure, les données stockée par notre composant storage peuvent être indexées par différents autres composants, comme les des btree qui permettent d'ordonner les données, des listes chaînées, ou encore des tables de hashage qui constituent des un système d'indexation.
Si les données référencées en terme de pointeurs par d'autres composants, il est dangereux de déplacer les données. Les pointeurs stockés dans les autres composants pointerait alors dans des zones non réservées pouvant contenir n'importe quoi et rendrait les autres composants caducs, voire dangereux.
Au lieu de réallouer par realloc, on utilisera plutôt un système paginé dont chaque page aura pour taille le produit de la taille d'un élément du stockage par le facteur de granularité défini plus haut.

Lorsque tous les éléments d'une page sont utilisés, on alloue une nouvelle page de grain * size.
On pourrait ajouter un système de libération atomique d'un élément. Cependant, ce genre de mécanisme ralentirait considérablement l'algorithme et reviendrait à utiliser les fonctions standard malloc() et free().
De plus, si un élément devient obsolète, il est toujours possible de le remplacer par un autre élément. Ceci peut être effectué par recopie d'un élément sur un autre, par un memcpy() vers le pointeur de l'élément obsolète, ou encore en modifiant les données directement quand le pointeur est interprèté par une structure.
La phase de destruction de l'espace de stockage se fait par libération de chaque page et non par libération de chaque élément.
En résumé, on tend à diminuer le nombre de malloc en allouant à chaque fois un certain nombre (grain) d'éléments à chaque fois. Plus le grain est grand, et moins on sera suceptible d'utiliser la fonction malloc(). A contrario, plus la granularité est grande, et plus on risque d'avoir de l'espace alloué mais non utilisé.
Ce composant permet de gérer des entités composées de nombreux éléments de taille identique, comme les tables d'une base de données. On ne pourra pas éliminer un élément de la table de manière atomique, mais on pourra toujours le modifier de manière atomique.

Architecture du composant storage

Notes préliminaires

Notre composant a pour but de stocker des entités composées d'éléments identiques de façon rapide et efficace. Elle doit décharger son utilisateur de la notion de gestion de la mémoire.

Contraintes primaires

Pas d'a priori sur le contenu

La notion de généricité nécessitent impérativement de ne pas avoir d'a priori sur le type des données à stocker. Ce point peut être géré en C++ par l'utilisation de types paramétres ou « templates ». En C, il suffira d'utiliser la notion de type générique représentée par void * et de savoir ce que l'on en fait.

Garantie de l'immobilité des données

Il est impératif de garantir l'abscence de déplacement des données stockées. En effet, comme nous l'avons vu plus haut, les données peuvent être utilisées à plusieurs endroits indépendants et référencées par différents composant. Tout déplacement au cours de l'exécution du programme entraînerait la perte des informations réféncées.

Facilité d'utilisation

Ce composant doit apporter une réelle valeur ajoutée en simplifiant de maniète importante la gestion de la mémoire. L'interface doit donc être la plus simple et la plus dépouillée possible.

Contrainte secondaire structurante

Enfin, il est nécessaire de prendre en compte la possibilité de multithreading. Cette contrainte n'est pas une contrainte primaire, mais elle ajoute des restriction structurantes au programme.
Nous devons en effet tenir compte des verrous mutuellements exclusifs (mutex locks), et nous devons nous arranger pour empêcher toute opération directe sur la structure de données. Il est donc nécessaire de cacher la structure aux programmes utilisateurs et de définir toutes les méthodes modifiant ou lisant les paramètres « visibles » du composant.

Structuration des données

Notre structure de base doit contenir des éléments invariant pendant toutes la durée de vie du composant. Ces données invariantes sont : la taille d'un élément et la granularité.
La structure doit aussi contenir des éléments variables. Ceux-ci sont : le nombre d'éléments alloués, la nombre d'éléments utilisés, le nombre de pages, et le tableau de pages. Enfin, pour la partie

L'interface

« Constructeur » et « destructeur »

/* Constructor: */
pstorage_t storage_new(size_t unit, size_t grain);

/* Destructor :*/
pstorage_t storage_destroy(pstorage_t ps);

Ajout d'éléments

char * storage_add(pstorage_t ps, char *pdata);

Récupération d'un élément du « tableau »

char * storage_get(pstorage_t ps, int i);

Information et supervision

int storage_used(pstorage_t ps);

int storage_allocated(pstorage_t ps);

int storage_available(pstorage_t ps);

int storage_grain(pstorage_t ps);

int storage_unit(pstorage_t ps);

Limitations

Conclusion