Gestion de mémoire par régions

En informatique, la gestion de mémoire par région est un type de gestion de mémoire avec lequel chaque objet alloué est assigné à une région. Une région, alias une zone, une arène, ou un contexte mémoire, est une collection d’objets alloués qui peut être efficacement désallouée en bloc. Comme l’allocation par pile, les régions facilitent l’allocation et la désallocation de la mémoire à faible coût ; mais elles sont plus flexibles, permettant aux objets de vivre plus longtemps que la pile d’activation dans laquelle ils ont été alloués. Dans une implémentation typique, tous les objets d'une région sont alloués dans une plage contiguë d’adresses mémoire.

Comme exemple simple, examinons le pseudocode suivant, qui alloue et puis désalloue une structure de donnée de type liste chaînée :

r ← créeRégion()
ListeDeNœuds tête ← null
pour i de 1 à 1000
    nouveauNœud ← alloueDansRégion(r, tailleDe(ListeDeNœuds))
    nouveauNœud.next ← tête
    tête ← nouveauNœud
détruitRégion(r)

Bien que la construction de la liste chaînée requiert beaucoup d’opérations, elle peut être rapidement détruite par une unique opération, en détruisant la région dans laquelle ses nœuds ont été alloués. Il n’est pas nécessaire de parcourir la liste entière pour cela.

Implémentation

L’implémentation de régions simples explicites est triviale ; la description suivante est basée sur Hanson^[1]. Chaque région est implémentée comme une liste chaînée de vastes blocs de mémoire ; chaque bloc devrait être assez grand pour permettre beaucoup d’allocations. Le bloc courant comporte un pointeur vers sa prochaine position libre, et si le bloc est plein, un nouveau bloc est alloué et ajouté à la liste chaînée. Quand la région est désallouée, le pointeur vers la prochaine position libre pointe à nouveau sur le premier bloc, et la liste des blocs peut être réutilisée pour une région ultérieurement créée. Alternativement, quand une région est désallouée, sa liste de blocs peut être ajoutée en fin d’une liste globale de blocs disponibles dans laquelle d’autres régions peuvent ultérieurement allouer de nouveaux blocs. Par ce procédé simple, il n’est pas possible de désallouer des objets individuels dans une région.

Le coût total par octet alloué par ce procédé est très faible ; presque toutes les allocations ne demandent qu’une comparaison et une mise à jour de pointeur vers la prochaine position libre. La désallocation d’une région est une opération à durée fixe et est rarement effectuée. Contrairement aux systèmes classiques de ramasse-miettes (informatique), il n’est pas nécessaire d’étiqueter les données avec leur type.

Histoire et concepts

Le concept de base des régions est très ancien, sa première apparition date de 1967 dans le paquetage de stockage libre AED de Douglas T. Ross, dans lequel la mémoire était partitionnée en une hiérarchie de zones ; chaque zone avait son propre alloueur et une zone pouvait être libérée en une fois, rendant ces zones utilisables comme régions^[2]. En 1990, Hanson démontra que les régions explicites en C (qu’il appelait arènes) offraient une performance par octet alloué supérieure au plus rapide des mécanismes d’allocation par tas binaire^[1]. Les régions explicites étaient partie intégrante de la conception de nombreux projets précoces de logiciels écrits en C, au nombre desquels le serveur HTTP Apache, qui les appelle arènes, et le SGBD PostgreSQL, qui les appelle contextes mémoriels^[3]. Comme l’allocation par tas binaire traditionnelle, ce procédé ne garantit pas la sécurité mémoire ; il est possible pour un programmeur d’accéder à une région, après qu’elle a été désallouée, par un pointeur pendant, ou bien d’oublier de désallouer une région, provoquant une fuite de mémoire.

Inférence de régions

En 1988, des chercheurs commencèrent à étudier comme utiliser les régions pour une allocation sécurisée de la mémoire en introduisant le concept d’inférence de région, où la création et la désallocation de régions, tout comme l’affectation d’expressions d’allocation statique individuelle à des régions précises, sont insérées par le compilateur au moment de la compilation. Le compilateur en est capable de façon à garantir que les pointeurs pendants et les fuites mémoires ne se produisent pas.

Dans les premiers travaux de Ruggieri et Murtagh^[4], une région est créée au début de chaque fonction et désallouée à la fin. Ils effectuent alors une analyse de flux de données pour déterminer la durée de vie de chaque expression d’allocation statique et l’assignent à la région la plus récente qui inclut sa durée de vie complète.

En 1994 ce travail fut généralisé par un travail fécond de Tofte et Talpin pour prendre en charge le polymorphisme de type et les fonctions d'ordre supérieur dans Standard ML, un langage de programmation fonctionnelle qui utilise un algorithme différent basé sur l’inférence de types et les concepts théoriques de types de région polymorphiques et de calcul de région^[5],[6]. Leurs travaux introduisirent une extension du λ-calcul qui inclut les régions en ajoutant deux constructions :

e₁ at ρ : calcule le résultat de l’expression e₁ et la stocke dans la région ρ;

letregion ρ in e₂ end : Crée une région and la lie à ρ ; évalue e₂; et désalloue la région.

À cause de cette structure syntaxique, les régions sont imbriquées, c’est-à-dire que si r₂ est créée après r₁, elle doit aussi être désallouée avant r₁ ; cela équivaut à une pile de régions. De plus, les régions doivent être désallouées par la fonction même dans laquelle elles sont créées. Ces restrictions ont été abandonnées par Aiken et al.^[7].

Ce λ-calcule devait servir comme une représentation intermédiaire prouvant la sécurité mémoire de programmes compilés de Standard ML vers du code machine, mais la construction d’un traducteur qui produise de bons résultats avec de gros programmes a fait face à nombre de limitations pratiques qui nécessitaient de nouvelles analyses pour être résolues, en particulier les appels récursifs, les récursions terminales et l’élimination des régions ne contenant qu’une valeur isolée. Ce travail fut complété en 1995^[8] et intégré dans le Kit ML Kit, une version de ML basée sur l’allocation par région à la place du ramasse-miettes. Ceci permit une comparaison directe entre deux des programmes-tests de taille moyenne, produisant des résultats très variables (« entre 10 fois plus rapide de quatre fois plus lent ») selon que le programme tirait parti ou non des régions ; les temps de compilation, cependant, étaient de l’ordre de plusieurs minutes^[9]. Le Kit ML a finalement été utilisé avec de grosses applications avec deux additions : un mécanisme pour compiler séparément les modules et une technique hybride combinant l’inférence de région avec un ramasse-miettes^[10],[11].

Généralisation à l’environnement de nouveaux langages

À la suite du développement du Kit ML, les régions ont commencé à être généralisées à l’environnement d’autres langages :

• Extensions diverses du langage de programmation C:
  • Le dialecte C « sécurisé » Cyclone qui, parmi bien d’autres caractéristiques, ajoute la prise en charge de régions explicites et évalue l’impact de la migration d’applications C existantes pour les utiliser^{[12],[13],[14]}.
  • Une extension de C applée RC^[15] a été implémentée qui utilise des régions gérées explicitement, mais utilise aussi le comptage de référence sur les régions pour garantir la sécurité mémoire en assurant qu’aucune région n’est libérée prématurément^[16],[17]. Regions decrease the overhead of reference counting, since references internal to regions don't require counts to be updated when they're modified. RC includes an explicit static type system for regions that allows some reference count updates to be eliminated^{[Quoi ?][18]}.
  • Une restriction de C appelée Control-C et qui force par construction les programmes à utiliser les régions (et une seule région à la fois) afin d’assurer statiquement la sécurité mémoire^[19].
• Les régions ont été implementées pour un sous-ensemble de Java^[20], et est devenu un composant critique de gestion de la mémoire pour Java temps réel, qui les combine avec les types de possession pour détecter l’encapsulation d’objets et éliminer les vérifications à l’exécution concernant la désallocation de régions^{[21],[22],[23]}. Plus récemment, un système semi-automatique a été proposé pour les régions inférantes dans des applications Java temps-réel embarquées, qui combine une analyse statique à la compilation, une politique d’allocation de régions à l’exécution et des indications venant du programmeur^[24],[25]. Les régions conviennent bien pour la programmation temps-réel car leur surcoût temporel est statiquement prédictible, sans la complexité des ramasse-miettes incrémentiels.
• Elles ont été implémentées pour les langages de programmation logique Prolog^{[26],[27],[28]} et Mercury^[29],[30] en étendant le modèle d’inférence de régions de Tofte and Talpin à la prise en charge la rétrospective et les abattements.

Désavantages

Les systèmes utilisant les régions peuvent être amenés à accumuler beaucoup de données (dont une proportion élevée de données mortes) dans les régions avant de pouvoir les désallouer ; ces cas sont communément appelés « fuites » (même si finalement ces régions sont libérées). Éliminer les fuites peut nécessiter de restructurer le programme, par exemple en introduisant de nouvelles régions à la durée de vie plus courte. Déboguer ce type de problème est particulièrement difficile avec des systèmes utilisant l’inférence de région : le programmeur doit alors comprendre l’algorithme d’inférence sous-jacent ou examiner la représentation intermédiaire commentée pour diagnostiquer le problème. Les ramasse-miettes traçants sont plus efficaces pour désallouer ce genre de données dans un temps raisonnable sans nécessiter pour autant de bouleverser la programmation ; cela a d’ailleurs été une justification des systèmes hybrides région/ramasse-miettes^[10]. D’un autre côté, les ramasse-miettes traçants peuvent aussi montrer des fuites subtiles, si des références aux données sont conservées alors qu’elles ne seront plus jamais utilisées.

La gestion de mémoire basée sur les régions marche mieux quand le nombre de régions est relativement petit et que chaque région contient beaucoup d’objets ; les programmes qui s’appuient sur beaucoup de régions clairsemées montreront des signes de fragmentation interne de mémoire, conduisant à un gâchis de mémoire et à un surcoût temporel pour la gestion des régions. À nouveau, en présence d’une inférence de régions, un tel problème peut être plus difficile à diagnostiquer.

Méthodes hybrides

Comme mentionné ci-dessus, RC utilise un hybride régions / comptage de référence qui limite le surcoût du comptage de références dans la mesure où les références internes aux régions ne nécessitent pas de comptage pour être mises à jour quand elles sont modifiées. De même, quelques méthode hybrides à marquage de région combinent les ramasse-miettes avec les régions ; elles fonctionnent en divisant le tas binaire en régions, en effectuant une passe balaie-marque dans laquelle chaque région contenant des objets vivants est marquée puis en libérant les régions non marquées. Cela nécessite une défragmentation continuelle pour rester efficace^[31].

Références

1. (en) David R. Hanson, « Fast allocation and deallocation of memory based on object lifetimes », Software: Practice and Experience, vol. 20, n^o 1,‎ 1989, p. 5–12 (DOI 10.1002/spe.4380200104, lire en ligne)
2. (en) Douglas Ross, « The AED free storage package », Communications of the ACM, vol. 10, n^o 8,‎ 1967, p. 481–492 (DOI 10.1145/363534.363546, lire en ligne)
3. 2010 PostgreSQL Global Development Group, « Section 41.3: Memory Management », PostgreSQL 8.2.15 Documentation, 1996 (consulté le 22 février 2010)
4. Cristina Ruggieri et Thomas P. Murtagh « Lifetime analysis of dynamically allocated objects » (1988) (DOI 10.1145/73560.73585, lire en ligne, consulté le 22 février 2010)
   — « (ibid.) », dans POPL '88: Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, New York, NY, USA, ACM
5. Modèle:Cite techreport^[Quoi ?] On Citeseer
6. Mads Tofte et Jean-Pierre Talpin « Implementation of the Typed Call-by-Value λ-calculus using a Stack of Regions » (1994) (DOI 10.1145/174675.177855, consulté le 22 février 2010)
   — « (ibid.) », dans POPL '94: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, New York, NY, USA, ACM (ISBN 0-89791-636-0), p. 188–201
7. Modèle:Cite techreport^[Quoi ?] On Citeseer
8. Lars Birkedal, Mads Tofte et Magnus Vejlstrup « From region inference to von Neumann machines via region representation inference » (1996) (DOI 10.1145/237721.237771, lire en ligne, consulté le 22 février 2010)
   — « (ibid.) », dans POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, New York, NY, USA, ACM (ISBN 0-89791-769-3), p. 171–183
9. (en) Mads Tofte, Lars Birkedal, Martin Elsman et Niels Hallenberg, « A Retrospective on Region-Based Memory Management », Higher Order Symbolic Computing, Hingham, MA, USA, Kluwer Academic Publishers, vol. 17, n^o 3,‎ 2004, p. 245–265 (ISSN 1388-3690, DOI 10.1023/B:LISP.0000029446.78563.a4, lire en ligne, consulté le 20 février 2009)
10. (en) Niels Hallenberg, Martin Elsman et Mads Tofte, « Combining region inference and garbage collection », SIGPLAN Notices, New York, NY, USA, ACM, vol. 37, n^o 5,‎ 2003, p. 141–152 (ISSN 0362-1340, DOI 10.1145/543552.512547, lire en ligne)
11. (en) Martin Elsman, « Garbage collection safety for region-based memory management », SIGPLAN Notices, New York, NY, USA, ACM, vol. 38, n^o 3,‎ 2003, p. 123–134 (ISSN 0362-1340, DOI 10.1145/640136.604190, lire en ligne)
12. « Cyclone: Introduction to Regions », Cyclone User Manual (consulté le 22 février 2010)
13. (en) Dan Grossman, Greg Morrisett, Trevor Jim, Michael Hicks et Yanling Wang, « Region-based memory management in cyclone », SIGPLAN Notices, vol. 37, n^o 5,‎ 2002, p. 282–293 (DOI 10.1145/543552.512563, lire en ligne)
14. Michael Hicks, Greg Morrisett et Dan Grossman « Experience with safe manual memory-management in cyclone » (2004) (DOI 10.1145/1029873.1029883, lire en ligne, consulté le 22 février 2010)
    — « (ibid.) », dans ISMM '04: Proceedings of the 4th international symposium on Memory management, New York, NY, USA, ACM (ISBN 1-58113-945-4), p. 73–84
15. David Gay, « RC - Safe, region-based memory-management for C »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}, David Gay's homepage, Intel Labs Berkeley, 1999 (consulté le 22 février 2010) « http://berkeley.intel-research.net/dgay/rc/index.html »^{(Archive.org • Wikiwix • Archive.is • Google • Que faire ?)}, octobre 2010
16. David Gay et Alex Aiken « Memory management with explicit regions » (1998) (DOI 10.1145/277650.277748, lire en ligne, consulté le 22 février 2010)
    — « (ibid.) », dans PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, New York, NY, USA, ACM (ISBN 0-89791-987-4), p. 313–323
17. David Edward Gay, Memory management with explicit regions (thèse), University of California at Berkeley, 2001 (lire en ligne)
18. (en) David Gay et Alex Aiken, « Language support for regions », SIGPLAN Notices, New York, NY, USA, ACM, vol. 36, n^o 5,‎ 2001, p. 70–80 (ISSN 0362-1340, DOI 10.1145/381694.378815, lire en ligne, consulté le 22 février 2010)
19. Sumant Kowshik, Dinakar Dhurjati et Vikram Adve « Ensuring code safety without runtime checks for real-time control systems » (2002) (DOI 10.1145/581630.581678, lire en ligne, consulté le 22 février 2010)
    — « (ibid.) », dans CASES '02: Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, New York, NY, USA, ACM (ISBN 1-58113-575-0), p. 288–297
20. Morten V. Christiansen, Region-based memory management in Java (thèse), Department of Computer Science (DIKU), University of Copenhagen, 1998 (lire en ligne)
21. William S. Beebee et Martin C. Rinard « An Implementation of Scoped Memory for Real-Time Java » (2001) (lire en ligne, consulté le 22 février 2010)
    — « (ibid.) », dans EMSOFT '01: Proceedings of the First International Workshop on Embedded Software, London, UK, Springer-Verlag (ISBN 3-540-42673-6), p. 289–305
22. Modèle:Cite techreport^[Quoi ?]
23. Chandrasekhar Boyapati, Alexandru Salcianu et William Beebee, Jr. « Ownership types for safe region-based memory management in real-time Java » (2003) (DOI 10.1145/781131.781168, lire en ligne, consulté le 22 février 2010)
    — « (ibid.) », dans PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, New York, NY, USA, ACM (ISBN 1-58113-662-5), p. 324–337
24. Chaker Nahkli, Christophe Rippert, Guillaume Salagnac et Sergio Yovine « Efficient region-based memory management for resource-limited real-time embedded systems » (2007) (lire en ligne, consulté le 22 février 2010)
    — « (ibid.) », dans Proceedings of "Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS'2006)"
25. Guillaume Salagnac et Christophe Rippert « Semi-Automatic Region-Based Memory Management for Real-Time Java Embedded Systems » (2007) (DOI 10.1109/RTCSA.2007.67, lire en ligne, consulté le 22 février 2010)
    — « (ibid.) », dans RTCSA '07: Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Washington, DC, USA, IEEE Computer Society (ISBN 0-7695-2975-5), p. 73–80
26. (en) Henning Makholm, « A region-based memory manager for prolog », SIGPLAN Notices, vol. 36, n^o 1,‎ 2001, p. 25–34 (DOI 10.1145/362426.362434, lire en ligne)
27. Henning Makholm, Region-based memory management in Prolog (thèse), University of Copenhagen, Denmark, 2000 (lire en ligne)
28. Henning Makholm « A region-based memory manager for prolog » (2000) (DOI 10.1145/362422.362434, lire en ligne, consulté le 22 février 2010)
    — « (ibid.) », dans ISMM '00: Proceedings of the 2nd international symposium on Memory management, New York, NY, USA, ACM (ISBN 1-58113-263-8), p. 25–34
29. (en) Quan Phan et Gerda Janssens, « Static region analysis for Mercury », Lecture Notes in Computer Science: Logic Programming, Springer Berlin / Heidelberg, vol. 4670/2007,‎ 2007, p. 317–332 (ISSN 1611-3349, DOI 10.1007/978-3-540-74610-2, lire en ligne, consulté le 22 février 2010)
30. Quan Phan et Zoltan Somogyi « Runtime support for region-based memory management in Mercury » (2008) (DOI 10.1145/1375634.1375644, consulté le 22 février 2010)
    — « (ibid.) », dans ISMM '08: Proceedings of the 7th international symposium on Memory management, New York, NY, USA, ACM (ISBN 978-1-60558-134-7), p. 61–70
31. Stephen M. Blackburn et Kathryn M. McKinley « Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance » (2008) (DOI 10.1145/1375581.1375586, consulté le 3 octobre 2010)
    — « (ibid.) », dans PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation, New York, NY, USA, ACM (ISBN 978-1-59593-860-2), p. 22–32

Sources

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Region-based memory management » (voir la liste des auteurs).

• Portail de l’informatique