Programmation:C:Memoire:Malloc
- Cette page est une sous-partie du cours Programmation:C:Memoire
Sommaire
Fonctionnement de malloc(3)
Cette section est un complément du tutorial sur malloc(3) cité précédement.
Principes généraux
Le rôle de l'allocateur malloc(3) est de réservé des zones de mémoire pour le programme, de gérer la taille du tas et si possible de maximiser l'usage de la mémoire allouée au processus.
Pour ce faire, malloc(3) doit organiser le tas. La version simple que l'on a écrit dans la section précédante (en utilisant sbrk(2)) n'est pas suffisante. En effet, on peut augmenter l'espace mémoire disponible, mais on ne peut pas le libérer. Il est également relativement compliquer d'effectuer les opérations nécessaires à realloc(3).
Il existe de nombreuse stratégie pour implanter malloc(3), mais elle partage toutes les mêmes points communs:
- les adresses sont alignés sur la taille des entiers;
- l'espace non utilisé en fin de tas est rendu au système;
- on conserve sous une forme ou une autre la taille du bloc réservé;
- les blocs libérés sont marqués afin d'être réutilisé plus tard.
Nous allons rapidement étudier l'implantation la plus simple: First Fit.
Implantation simple: First Fit
Méta-données
Pour implanter cette version de malloc(3), on ajoute au bloc réservé, une structure (placée avant) contenant les informations nécessaires: taille, disponibilité, adresse du bloc suivant, adresse du bloc précédant ...
La structure usuelle pour les méta-données est la suivante:
struct s_block { size_t size; struct s_block *next; struct s_block *prev; int free; void *ptr; /* A pointer to the allocated block */ char data[1]; };
- size: la taille du bloc alloué;
- next, prev: les pointeurs sur les méta-données des blocs suivants et précédants;
- free: indicateur de disponibilité du bloc;
- ptr: le pointeur sur les données, pour le contrôleur d'erreur de free;
- data un accès direct au bloc alloué sous forme de tableau de caractère (utile pour les opérations de copie et certaines addition de pointeur), ce champ n'occupe pas de place dans les méta-données.
Le tas devient ainsi une liste doublement chaînée de blocs mémoire de taille variable.
La recherche
Le principe de notre malloc(3) est simple: on cherche dans le tas un bloc libre suffisamment grand pour notre allocation à l'aide de l'adresse de début de tas et du chaînage que l'on vient de mettre en place.
L'algorithme de First Fit prend le premier bloc qui convient (d'où son nom.) Il engendre ainsi une certaine perte de mémoire. Pour compenser, on l'accompagne en règle générale, d'une opération split, qui va couper en deux le bloc trouvé si celui-ci est suffisamment grand.
free
L'opération de libération est relativement simple:
- Trouver les méta-données du bloc à liberer;
- Marquer le bloc comme libre.
Pour limiter les effets de la fragmentation, on ajoute une opération fusion dont le rôle est de reconstruire des blocs de taille plus importante. L'opération de fusion est relativement simple: si les blocs voisins sont libres, on les regroupe dans un seul grand bloc. En effectuant la fusion avec les deux voisins immédiats (avant et après) on s'assure qu'il n'y a jamais plus de un bloc libre consécutif.
L'opération de fusion nécessite de pouvoir accéder aux voisins, le pointeur sur le bloc précédant dans la structure est là pour ça.
La validation du pointeur à libérer et la récupération des méta-données nécessitent quelques petites astuces:
- On vérifie que le pointeur à libérer est bien un aligné;
- On vérifie que le pointeur se trouve bien dans la zone du tas gérer par malloc (entre le début du tas et le break.)
- Enfin, pour s'assurer que le pointeur correspond bien à un bloc, on va sauver l'adresse du bloc de donnée dans les méta-données. Ainsi, comme les méta-données sont immédiatement avant le bloc, il suffit de réculer de la taille de la structure et de comparer l'adresse à libérer et le champ (supposé) de la structure.
Les autres méthodes
L'algorithme First Fit est relativement simple à implanter et donne des performances acceptables, mais il souffre de nombreux défauts:
- Malgrès l'utilisation des opérations split et fusion, on perd beaucoup d'espace (dans les méta-données et dans la fragmentation.)
- La complexité en temps de la recherche de bloc est liée aux nombre de blocs (libres ou non) et de nombreuse recherche de blocs impliquent un parcours complet du tas.
- L'organisation du tas ne tient pas compte de la différence des opérations effectuées sur les blocs libres et les blocs utilisées.
- Le principe de First Fit est un peu trop simple: il pourrait être plus judicieux de prendre un bloc de taille proche que de prendre le premier qui vient et de le spliter.
- Cette stratégie n'est pas thread-friendly (on peut la rendre thread-safe simplement par contre.)
Il existe de nombreux approches pour améliorer l'implantation de malloc:
- Utilisation d'un tas circulaire: le dernier bloc référence le premier blocs comme successeur et les différentes opérations de recherche commence sur le dernier bloc traités. C'est la stratégie utilisée dans le malloc présenté dans le K&R[1].
- Approche Best Fit: on cherche le meilleur bloc plutôt que le premier qui vient. L'implantation naïve de cette approche est pire qu'un First Fit en terme de complexité mais diminue grandement la fragmentation du tas.
- Variation sur l'approche Best Fit: en règle générale, les algorithmes d'allocation implémente une forme de Best Fit où un chaînage intelligent des blocs fait disparaître le surcoût de la recherche. Dans les techniques classiques utilisées on peut citer:
- Chaînages des blocs libres indépendants (peut être util aussi pour améliorer un First Fit.)
- Chaînages des blocs par taille
- Construction hiérarchique des blocs: les blocs sont tous obtenue par division par deux de blocs plus grands ou par fusion de blocs issues du même bloc d'origine.
- L'algorithme dit des Buddy est basé sur des principes similaires à ceux évoqués plus haut. C'est l'un des algorithmes les plus utilisés. Une bonne présentation de cette technique peut être trouvée dans le TAOCP[2], ou dans l'article original[3].
- Il existe encore beaucoup d'autre méthode comme les Slab Allocator ou d'autres méthodes hybrides répondant à des besoins spécifiques ou simplement essayant de tirer le meilleur des différentes approches.
Les véritables implantation de malloc utilisent en général des variantes hybrides de ces différentes techniques avec quelques adaptations pour répondre aux problèmes matériels ou systèmes que les versions théoriques des ces algorithmes ne prennent pas forcément en compte (comme la séparation des méta-données pour éviter les échecs de pages et de cache à répétition.)
Pour aller plus loin
- jemalloc de FreeBSD[4]
- dlmalloc utilisé dans la glibc[5]
- phkmalloc de FreeBSD (avant la version 7)[6]
- tcmalloc de google[7]
Référence
- ↑ Brian W. Kernighan and Dennis M. Ritchie, "The C Programming Language", 1978 (ISBN 0-13-110163-3 (1ed) et (ISBN 0-13-110362-8 (2ed))
- ↑ Donald Knuth (1997): The Art of Computer Programming Volume 1: Fundamental Algorithms Second Edition. Reading, Massachusetts: Addison-Wesley. pp. 435-455. ISBN 0-201-89683-4.
- ↑ Kenneth C. Knowlton. A Fast storage allocator. Communications of the ACM 8(10):623-625, Oct 1965. Et Kenneth C Knowlton. A programmer's description of L6. Communications of the ACM, 9(8):616-625, Aug. 1966
- ↑ Jason Evans. A Scalable Concurrent malloc(3) Implementation for FreeBSD [1]
- ↑ Doug Lea. A Memory Allocator [2]
- ↑ Kamp, Poul-Henning. Malloc(3) revisited, 193-198. USENIX 1998 Annual Technical Conference: Invited Talks and Freenix Track. New Orleans, LA, June 15-19, 1998. Berkeley, CA: USENIX Association, 1998.
- ↑ Sanjay Ghemawat et Paul Menage. TCMalloc : Thread-Caching Malloc [3]
| Cours | Partie |
|---|---|
| Cours de Programmation EPITA/spé | Programmation:C |
