Résumé
Voici le dernier article de cette longue série de 24 qui a durée un peu plus de deux années. Nous finissons notre allocateur de mémoire en C avec les dernière fonctions qui restaient en suspens.
En effet, ma nouvelle fonction chez Tornado Technology ne permet plus de soutenir le rythme de deux articles par mois. J'espère sincèrement que ces articles auront permis à certains de découvrir le langage C de manière pratique et donné le goût à l'écriture de logiciels en C.
Je remercie tous les lecteurs qui m'ont soutenu et corrigé les (quelques :-) erreurs qui se sont glissées de temps en temps. Je remercie aussi Linux Magazine, son rédacteur Denis Bodor et toute l'équipe d'ouvrir leurs colonnes de cette manière et d'avoir la patience de relire, corriger et mettre en forme nos textes.
Il me reste maintenant à rassembler tout ce matériel en un livre qui sera placé sur le WEB et disponible librement pour tous.
Un hommage maintenant : ces articles ont été écrits sur un portable sous Linux Slackware (www.slackware.com), en utilisant la suite bureautique Applixware (www.applixware.com) qui à su, sans broncher, transcrire mon blabla. La correction grammaticale a été assurée par Corector101 (www.machinasapiens.com) qui laisse loin derrière les autres correcteurs. L'ensemble de ces trois outils revient à moins de 1000 francs, soit 152,43 euro, ou 20 places de cinéma. Deux choses : je n'ai aucune actions ni chez l'un ni chez l'autre, et je ne vois pas pourquoi je ne dirais pas ce que j'en pense car il est temps de faire savoir que l'on peut travailler correctement dans un environnement Linux, même en bureautique. Ces éloges ne diminuent cependant en rien la qualité des autres solutions, libres ou non.
Quant à moi, je continue les articles sur le langage Scheme (sauf ce mois-ci) en finissant le serveur WEB, puis j'entamerai une nouvelle série d'articles destinée à présenter la 3D en Scheme, en utilisant scrupuleusement la norme R4/5RS de manière à ce que le code soit exécutable par la plupart des environnements Scheme, dont OpenScheme.
Description
Le mois dernier, nous avons présenté un allocateur de mémoire dynamique qui permet de gérer la ressource 'mémoire' de manière optimale. Il nous reste à terminer cet allocateur en réalisant la fonction de libération de blocs, et les fonctions d'allocation secondaires, basées sur la fonction d'allocation présentée le mois dernier.
Nous montrerons ensuite comment utiliser cette bibliothèque de manière automatique à l'aide d'un jeu de macros.
Réalisation de la bibliothèque
Libération
La libération des blocs alloués consiste à permettre au bloc d'être à nouveau alloué en le replaçant dans la liste des blocs libres. Si on n'y prend pas garde, la mémoire va se trouver morcelée en blocs de plus en plus petits au fil de son utilisation. La fonction de désallocation essaye de palier à cet inconvénient en vérifiant si le bloc désalloué ne peut pas être associé à un bloc libre placé avant ou après lui, ou les deux :
/*
Libération d'un bloc de mémoire. */
void
heap_free (char * pointer) {
Header p, q;
/*
Si le pointeur est nul, provoquer
* une erreur. C'est le
comportement
* standardisé par l'ANSI.
*/
if (! pointer) {
abort();
}
/* Supprimer le pointeur du tableau
* de pointeurs */
_debug_heap_del (pointer);
/* Récupérer
l'entête */
p = (Header) pointer - 1;
_current -=
p->s.size;
/* Recherche du bloc libre situé
juste
* avant le bloc à libérer
*/
for (q =_allocp;
! (p > q &&
p < q->s.ptr);
q = q->s.ptr) {
if (q
>= q->s.ptr &&
(p > q || p <
q->s.ptr)) {
break;
}
}
/*
si les blocs sont adjacents, les
* joindre */
if (p + p->s.size == q->s.ptr) {
p->s.size +=
q->s.ptr->s.size;
p->s.ptr = q->s.ptr->s.ptr;
}
else {
p->s.ptr = q->s.ptr;
}
if
(q + q->s.size == p) {
q->s.size += p->s.size;
q->s.ptr = p->s.ptr;
}
else {
q->s.ptr
= p;
}
_allocp = q;
}
La fonction de libération recherche dans la liste des blocs libres le bloc situé juste avant le bloc à libérer. Elle tente ensuite de relier le bloc à libérer aux blocs adjacents situés avant et après lui de manière à limiter le morcellement de la mémoire.
Allocation avec initialisation à zéro
Voici maintenant la réalisation de la fonction équivalente à calloc :
/*
Équivalent de la fonction calloc */
char *
heap_calloc (unsigned size,
unsigned
number) {
/* Calculer la taille demandée */
unsigned s = size * number;
/* Allouer de la
mémoire non initialisée */
char * p
= (char *) heap_malloc (s);
if (p) {
/*
Initialiser la mémoire */
memset (p, 0,
s);
}
/* Retourner le pointeur */
return
(p);
}
Cette fonction se contente de calculer la taille du bloc, de l'allouer et de l'initialiser à zéro.
Réallocation
Notre fonction de réallocation est une version simplifiée qui, en fait, alloue toujours un nouvel objet au lieu de tenter d'agrandir la taille du bloc déjà alloué :
/*
Équivalent de la fonction realloc */
char *
heap_realloc (char * pointer,
unsigned size) {
unsigned old;
char *
ptr = heap_malloc (size);
if (pointer) {
/*
Calculer la taille de l'ancien bloc */
old = ((Header)
pointer - 1) -> s.size;
memcpy (ptr, pointer, size >
old ? old : size);
}
/* Retourner le pointeur */
return (ptr);
}
Il faudrait que cette fonction vérifie la présence d'un espace libre suffisamment grand situé juste après le bloc. Si cet espace existe, l'espace libre est scindé en deux et la taille du bloc mise à jour. Si cet espace n'existe pas, la fonction d'allocation est invoquée et un nouveau bloc est retourné, comme c'est le cas maintenant.
Taille d'un bloc
Cette fonction permet d'obtenir la taille d'un bloc de mémoire. Cette fonction n'a pas d'équivalence dans la norme ANSI :
/*
Retourne la taille d'un bloc. */
unsigned heap_size
(char * pointer) {
if (! pointer) {
return
(0);
}
return (((Header) pointer - 1) ->
s.size);
}
Obtention de statistiques
Cette fonction permet d'obtenir les statistiques concernant l'utilisation de la mémoire :
/*
Retourne les statistiques concernant
* le tas. */
void
heap_stats (unsigned * current,
unsigned
* maximum,
double * total,
unsigned * mallocs) {
(* current) = _current;
(*
maximum) = _maximum;
(* total) = _total;
(* mallocs) =
_mallocs;
}
Les valeurs retournées sont placées dans les arguments pointeurs. On retourne le nombre d'octets actuellement alloués, le maximum d'octets qui furent alloués simultanément, le cumul du nombre d'octets alloués et le nombre d'allocations effectuées.
Ces statistiques permettent notamment de savoir s'il reste des blocs alloués et non libérés.
Utilisation
Pour utiliser les fonctions de cette bibliothèque de manière transparente à la place des fonctions standards, il est possible de modifier légèrement le fichier d'entête :
#ifndef
___HEAP_H
#define ___HEAP_H
void
heap_init (unsigned heap_size);
void
heap_end (void);
char * heap_malloc
(unsigned nbytes);
char * heap_calloc
(unsigned size,
unsigned
number);
char * heap_realloc (char *
pointer,
unsigned size);
void
heap_free (char * pointer);
unsigned
heap_size (char * pointer);
void
heap_stats (unsigned * current,
unsigned * maximum,
double
* total,
unsigned *
mallocs);
#ifdef
HEAP_DEBUG
# define
malloc(n) heap_malloc(n)
#
define calloc(s,n) heap_calloc
((s), (n))
# define
realloc(p,s) heap_realloc ((p), (s))
#
define free(p)
heap_free(p)
#endif
/* HEAP_DEBUG */
#endif
/* ___HEAP_H */
L'inclusion de ce fichier sera faite avant toute autre inclusion. Lorsque la macro DEBUG_HEAP sera définie, en ajoutant l'option -D DEBUG_HEAP sur la ligne de commande de gcc, nos fonctions d'allocation seront utilisées en lieu et place des fonctions standards.
Améliorations
On pourra modifier notre fonction d'allocation pour que des mots magiques soient placés juste avant et juste après le bloc de mémoire retourné à l'utilisateur. La fonction de libération devra vérifier que les mots magiques sont toujours présents ; si ce n'est pas le cas, le programme utilisateur aura commit une erreur mémoire et si c'est le cas, on est sûrs de rien.
Figure
1: Utilisation de mots magiques pour contrôler les
débordements dans l'écriture du bloc de mémoire.
Ce contrôle est partiel et ne détecte que les débordements en écriture et non en lecture. Pour effectuer des vérifications strictes, on pourra utiliser la bibliothèque ElectricFence de Bruce Perens (www.perens.com) qui détecte tout débordement tant à la lecture qu'à l'écriture.
L'allocation de blocs de taille constante est plus simple et plus efficace que l'allocation de blocs de taille variable. On pourra modifier l'allocateur pour que pour les tailles allant, par exemple, de 1 à 100 octets, une gestion spécifique soit réalisée de manière à optimiser l'allocateur.
Voila maintenant terminé notre allocateur de mémoire simpliste.
Il me reste à vous remercier de vos lectures attentives et à vous souhaiter bonne route ...
L'auteur
Guilhem de Wailly, gérant de la société Erian Concept, partenaire NetUltra (www.netultra.net) et Getek (www.getek.fr) et Vice-Président R&D de Tornado Technology (www.aecviz.com).
|
|
Votre interlocuteur Linux ! Support, formations, configurations, administration, développements Linux. http://www.erian-concept.com |
Références
Langage C - norme ANSI : bon ouvrage de référence
Ph.
DRIX
Masson
Programmer en C++: une bonne référence
S.C.
DEWHURST et K.T. STARK
Masson
Le Langage C: la bible!
B.W. KERNIGHAN et D.M.
RITCHIE
Masson
gcc: compilateur C du GNU, et tous les outils de
développement
http://www.gnu.org
Kdevel: un environnement KDE de programmation
C
http://samuel.cs.uni-potsdam.de/~smeier/kdevelop_new/index.html