Region-based memory management: Difference between revisions

Revision as of 13:40, 29 January 2023

Latest revision as of 04:16, 15 August 2025

(31 intermediate revisions by 14 users not shown)

Line 1:

{{Short description|Memory allocation scheme}}

{{Use American English|date = February 2019}}

In [[computer science]], '''region-based memory management''' is a type of [[memory management]] in which each allocated object is assigned to a '''region'''. A region, also called a '''partition''', '''subpool''', '''zone''', '''arena''', '''area''', or '''memory context''', is a collection of allocated objects that can be efficiently reallocated or deallocated all at once. LikeMemory [[stackallocators allocation]],using regionsregion-based facilitatemanagements allocationare andoften deallocationcalled of'''area memory with low overhead; but they are more flexibleallocators''', allowingand objects to live longer than the [[stack frame]] in whichwhen they werework allocated.by Inonly typical implementations, all objects in a region are allocated in"bumping" a single contiguous range of memory addressespointer, similarlyas to'''bump how stack frames are typically allocatedallocators'''.

{{Short description|Memory allocation scheme}}

In [[computer science]], '''region-based memory management''' is a type of [[memory management]] in which each allocated object is assigned to a '''region'''. A region, also called a '''zone''', '''arena''', '''area''', or '''memory context''', is a collection of allocated objects that can be efficiently reallocated or deallocated all at once. Like [[stack allocation]], regions facilitate allocation and deallocation of memory with low overhead; but they are more flexible, allowing objects to live longer than the [[stack frame]] in which they were allocated. In typical implementations, all objects in a region are allocated in a single contiguous range of memory addresses, similarly to how stack frames are typically allocated.

== Example ==

As a simple example, consider the following [[C (programming language)|C]] code which allocates and then deallocates a [[linked list]] data structure:

Like [[stack allocation]], regions facilitate allocation and deallocation of memory with low overhead; but they are more flexible, allowing objects to live longer than the [[stack frame]] in which they were allocated. In typical implementations, all objects in a region are allocated in a single contiguous range of memory addresses, similarly to how stack frames are typically allocated.

<syntaxhighlight lang="c">

Region *r = createRegion();

ListNode *head = NULL;

for (int i = 1; i <= 1000; i++) {

ListNode* newNode = allocateFromRegion(r, sizeof(ListNode));

newNode->next = head;

head = newNode;

}

// ...

// (use list here)

// ...

destroyRegion(r);

</syntaxhighlight>

In [[OS/360 and successors]], the concept applies at two levels; each job runs within a contiguous partition{{efn|For [[OS/360 and successors#MFT|MFT]] and [[OS/VS1]]}} or region.{{efn|For [[OS/360 and successors#MVT|MVT]], [[OS/VS2]] and later [[MVS]] systems.}} Storage allocation requests specify a subpool, and the application can free an entire subpool. Storage for a subpool is allocated from the region or partition in blocks that are a multiple of 2 KiB{{efn|For OS/360 and OS/VS1}} or 4 KiB{{efn|For OS/VS2 and later MVS systems.}} that generally are not contiguous.

Although it required many operations to construct the linked list, it can be quickly deallocated in a single operation by destroying the region in which the nodes were allocated. There is no need to traverse the list.

== Implementation ==

Simple explicit regions are straightforward to implement; the following description is based on the work of Hanson.<ref name="hanson">

{{cite journal |last1=Hanson |first1=David R. |year=1989 |title=Fast allocation and deallocation of memory based on object lifetimes |journal=Software: Practice and Experience |volume=20 |issue=1 |pages=5–12 |url=http://www3.interscience.wiley.com/journal/113446436/abstract?CRETRY=1&SRETRY=0 |archive-url=https://archive.today/20121020025006/http://www3.interscience.wiley.com/journal/113446436/abstract?CRETRY=1&SRETRY=0 |url-status=dead |archive-date=2012-10-20 |doi=10.1002/spe.4380200104 |s2cid=8960945 |url-access=subscription }}

</ref> Each region is implemented as a [[linked list]] of large blocks of memory; each block should be large enough to serve many allocations. The current block maintains a pointer to the next free position in the block, and if the block is filled, a new one is allocated and added to the list. When the region is deallocated, the next-free-position pointer is reset to the beginning of the first block, and the list of blocks can be reused for the next allocated region. Alternatively, when a region is deallocated, its list of blocks can be appended to a global freelist from which other regions may later allocate new blocks. With either case of this simple scheme, it is not possible to deallocate individual objects in regions.

Line 33 ⟶ 17:

== History and concepts ==

The basic concept of regions is very old, first appearing as early as 1967 in Douglas T. Ross's AED Free Storage Package, in which memory was partitioned into a hierarchy of zones; each zone had its own allocator, and a zone could be freed all-at-once, making zones usable as regions.<ref>

{{cite journal |last1=Ross |first1=Douglas |year=1967 |title=The AED free storage package |journal=Communications of the ACM |volume=10 |issue=8 |pages=481–492 |doi=10.1145/363534.363546 |s2cid=6572689 |doi-access=free }}

</ref> In 1976, the [[PL/I]] standard included the AREA data type.<ref>{{cite book|last=American National Standards Institute, inc.|title=American National Standard Programming Language PL/I|year=1976}}</ref> In 1990, Hanson demonstrated that explicit regions in C (which he called arenas{{WhatClarify|date=January 2022}}) could achieve time performance per allocated byte superior to even the fastest-known heap allocation mechanism.<ref name="hanson" /> Explicit regions were instrumental in the design of some early C-based software projects, including the [[Apache HTTP Server]], which calls them pools, and the [[PostgreSQL]] database management system, which calls them memory contexts.<ref>

{{cite web |url=http://www.postgresql.org/docs/8.2/static/spi-memory.html |title=Section 41.3: Memory Management |author=2010 PostgreSQL Global Development Group |year=1996 |work=PostgreSQL 8.2.15 Documentation |accessdate=22 February 2010}}

</ref> Like traditional heap allocation, these schemes do not provide [[memory safety]]; it is possible for a programmer to access a region after it is deallocated through a [[dangling pointer]], or to forget to deallocate a region, causing a [[memory leak]].

Line 46 ⟶ 30:

In 1994, this work was generalized in a seminal work by Tofte and Talpin to support [[type polymorphism]] and [[higher-order function]]s in [[Standard ML]], a [[functional programming]] language, using a different algorithm based on [[type inference]] and the theoretical concepts of polymorphic [[region type]]s and the [[region calculus]].<ref>

{{cite techreporttech report | title=A Theory of Stack Allocation in Polymorphically Typed Languages | last1=Tofte |first1=Mads |author2=Jean-Pierre Talpin | number=93/15 | institution=Department of Computer Science, Copenhagen University |year=1993}} [http://citeseer.ist.psu.edu/124242.html On Citeseer]

</ref><ref>

{{cite conference |title=Implementation of the Typed Call-by-Value λ-calculus using a Stack of Regions |last1=Tofte |first1=Mads |author-link1=Mads Tofte |last2=Talpin |first2=Jean-Pierre |author-link2=Jean-Pierre Talpin |year=1994 |book-title=POPL '94: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages |publisher=ACM |___location=New York, NY, USA |pages=188&ndash;201 |isbn=0-89791-636-0 |doi=10.1145/174675.177855 |url=https://books.google.com/books?id=k-zHGxDf-HgC&q=POPL+%2794:+Proceedings+of+the+21st+ACM+SIGPLAN-SIGACT+symposium+on+Principles+of+programming+languages |accessdate=15 April 2014|doi-access=free }}

Line 52 ⟶ 36:

:''e''₁ at ρ: Compute the result of the expression ''e''₁ and store it in region ρ;

:letregionlet region ρ in ''e''₂ end: Create a region and bind it to ρ; evaluate ''e''₂; then deallocate the region.

Due to this syntactic structure, regions are ''nested'', meaning that if r₂ is created after r₁, it must also be deallocated before r₁; the result is a ''stack'' of regions. Moreover, regions must be deallocated in the same function in which they are created. These restrictions were relaxed by Aiken et al.<ref>

{{cite techreporttech report | title=Better Static Memory Management: Improving Region-Based Analysis of Higher-Order Languages | last1=Aiken |first1=Alex |author2=Manuel Fähndrich, Raph Levien | number=UCB/CSD-95-866 | institution=EECS Department, University of California, Berkeley | year=1995}} [http://citeseer.ist.psu.edu/124242.html On Citeseer]

</ref>

This extended lambda calculus was intended to serve as a provably memory-safe [[intermediate representation]] for compiling Standard ML programs into machine code, but building a translator that would produce good results on large programs faced a number of practical limitations which had to be resolved with new analyses, including dealing with recursive calls, [[tail call]]s, and eliminating regions which contained only a single value. This work was completed in 1995<ref>

{{cite conference |url=http://portal.acm.org/citation.cfm?id=237721.237771 |title=From region inference to von Neumann machines via region representation inference |last1=Birkedal |first1=Lars |author-link1=Lars Birkedal |last2=Tofte |first2=Mads |author-link2=Mads Tofte |last3=Vejlstrup |first3=Magnus |author-link3=Magnus Vejlstrup |year=1996 |book-title=POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages |publisher=ACM |accessdate=22 February 2010 |pages=171&ndash;183 |___location=New York, NY, USA |isbn=0-89791-769-3 |doi=10.1145/237721.237771|doi-access=free }}

</ref> and integrated into the ML Kit, a version of ML based on region allocation in place of garbage collection. This permitted a direct comparison between the two on medium-sized test programs, yielding widely varying results ("between 10 times faster and four times slower") depending on how "region-friendly" the program was; compile times, however, were on the order of minutes.<ref>

{{cite journal |last1=Tofte |first1=Mads |last2=Birkedal |first2=Lars |last3=Elsman |first3=Martin |last4=Hallenberg |first4=Niels |year=2004 |title=A Retrospective on Region-Based Memory Management |journal=Higher Order Symbolic Computing |volume=17 |issue=3 |pages=245&ndash;265 |issn=1388-3690 |doi=10.1023/B:LISP.0000029446.78563.a4 |doi-access=free }}

Line 81 ⟶ 65:

** An extension to C called RC<ref>{{cite web|url=http://berkeley.intel-research.net/dgay/rc/index.html |title=RC - Safe, region-based memory-management for C |last1=Gay |first1=David |year=1999 |work=David Gay's homepage |publisher=Intel Labs Berkeley |accessdate=22 February 2010 |url-status=dead |archive-url=https://web.archive.org/web/20090226070550/http://berkeley.intel-research.net/dgay/rc/index.html |archive-date=February 26, 2009 }}

</ref> was implemented that uses explicitly-managed regions, but also uses [[reference counting]] on regions to guarantee memory safety by ensuring that no region is freed prematurely.<ref>

{{cite conference |url=http://portal.acm.org/citation.cfm?id=277650.277748 |title=Memory management with explicit regions |last1=Gay |first1=David |author-link1=David Gay (mathematician) |last2=Aiken |first2=Alex |author-link2=Alex Aiken |year=1998 |book-title=PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation |publisher=ACM |___location=New York, NY, USA |accessdate=22 February 2010 |pages=313&ndash;323 |isbn=0-89791-987-4 |doi=10.1145/277650.277748|url-access=subscription }}

</ref><ref>

{{Cite thesis |degree=PhD in Computer Science |title=Memory management with explicit regions |url=http://theory.stanford.edu/~aiken/publications/theses/gay.pdf |last=Gay |first=David Edward |year=2001 |publisher=University of California at Berkeley |accessdate=20 February 2010}}

Line 88 ⟶ 72:

</ref>

** A restriction of C called Control-C limits programs to use regions (and only a single region at a time), as part of its design to statically ensure memory safety.<ref>

{{cite conference |url=http://portal.acm.org/citation.cfm?id=581678 |title=Ensuring code safety without runtime checks for real-time control systems |last1=Kowshik |first1=Sumant |last2=Dhurjati |first2=Dinakar |last3=Adve |first3=Vikram |year=2002 |publisher=ACM |___location=New York, NY, USA |accessdate=22 February 2010 |book-title=CASES '02: Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems |pages=288&ndash;297 |isbn=1-58113-575-0 |doi=10.1145/581630.581678|url-access=subscription }}

</ref>

* Regions were implemented for a subset of [[Java (programming language)|Java]],<ref>

{{Cite thesis |degree=Masters in Computer ScienceFTP |title=Region-based memory management in Java |url=ftp://ftp.diku.dk/diku/semantics/papers/D-395.ps.gz |last=Christiansen |first=Morten V. |year=1998 |publisherserver=Department of Computer Science (DIKU), University of Copenhagen |url-status=dead |accessdate=20 February 2010 }}{{dead link|date=April 2018 |bot=InternetArchiveBot |fix-attempted=yes }}

</ref> and became a critical component of memory management in [[Real time Java]], which combines them with [[ownership type]]s to demonstrate object encapsulation and eliminate runtime checks on region deallocation.<ref>{{cite conference |url=http://www.cag.lcs.mit.edu/~rinard/paper/emsoft01.ps |title=An Implementation of Scoped Memory for Real-Time Java |last1=Beebee |first1=William S. |last2=Rinard |first2=Martin C. |year=2001 |publisher=Springer-Verlag |___location=London, UK |accessdate=22 February 2010 |book-title=EMSOFT '01: Proceedings of the First International Workshop on Embedded Software |pages=289&ndash;305 |isbn=3-540-42673-6 }}{{Dead link|date=February 2020 |bot=InternetArchiveBot |fix-attempted=yes }}</ref><ref>

{{cite techreporttech report | title=A type system for safe region-based memory management in Real-Time Java | last1=Sălcianu |first1=Alexandru |author2=Chandrasekhar Boyapati, William Beebee, Jr., Martin Rinard |number=MIT-LCS-TR-869 | institution=MIT Laboratory for Computer Science |year=2003 |url=http://people.csail.mit.edu/rinard/techreport/MIT-LCS-TR-869.pdf}}

</ref><ref>

{{cite conference |url=http://portal.acm.org/citation.cfm?id=781168 |title=Ownership types for safe region-based memory management in real-time Java |last1=Boyapati |first1=Chandrasekhar |author-link1=Chandrasekhar Boyapati|last2=Salcianu |first2=Alexandru |author-link2=Alexandru Salcianu|last3=Beebee, Jr. |first3=William Jr.|author-link3=William Beebee, Jr.|year=2003 |publisher=ACM |___location=New York, NY, USA |accessdate=22 February 2010 |book-title=PLDI '03: Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation |pages=324&ndash;337 |isbn=1-58113-662-5|doi=10.1145/781131.781168|url-access=subscription }}

</ref> More recently, a semi-automatic system was proposed for inferring regions in embedded real-time Java applications, combining a compile-time static analysis, a runtime region allocation policy, and programmer hints.<ref>

{{cite conference |url=http://hal.inria.fr/docs/00/30/96/88/PDF/06-Salagnac-ICOOOLPS.pdf |title=Efficient region-based memory management for resource-limited real-time embedded systems |last1=Nahkli |first1=Chaker |author-link1=Guillaume Salagnac |last2=Rippert |first2=Christophe |author-link2=Christophe Rippert |last3=Salagnac |first3=Guillaume |author-link3=Guillaume Salagnac |last4=Yovine |first4=Sergio |year=2007 |accessdate=22 February 2010 |book-title=Proceedings of "Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS'2006)"}}

Line 101 ⟶ 85:

{{cite conference |title=Semi-Automatic Region-Based Memory Management for Real-Time Java Embedded Systems |last1=Salagnac |first1=Guillaume |author-link1=Guillaume Salagnac|last2=Rippert |first2=Christophe |author-link2=Christophe Rippert|year=2007 |publisher=IEEE Computer Society |___location=Washington, DC, USA |book-title=RTCSA '07: Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications |pages=73&ndash;80 |isbn=978-0-7695-2975-2|doi=10.1109/RTCSA.2007.67}}

</ref> Regions are a good fit for [[real-time computing]] because their time overhead is statically predictable, without the complexity of incremental garbage collection.

* Java 21 added a Java API to allocate and release Arenas.<ref>{{cite web |title=Memory Segments and Arenas |url=https://docs.oracle.com/en/java/javase/21/core/memory-segments-and-arenas.html#GUID-01CE34E8-7BCB-4540-92C4-E127C1F62711 |publisher=Oracle}}</ref> The stated purpose of these is to improve safe integration with native libraries so as to prevent JVM memory leaks and to reduce the risk of JVM memory corruption by native code.<ref>{{cite web |last1=Cimadamore |first1=Maurizio |title=JEP 454: Foreign Function & Memory API |url=https://openjdk.org/jeps/454 |publisher=OpenJDK}}</ref> Arenas are a part of the Java Foreign Function and Memory Interface, which is a successor to [[Java Native Interface]] (JNI), and includes classes like <code>Arena</code>, <code>MemorySegment</code>, and others.<ref>{{cite web|title=Package java.lang.foreign|url=https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/lang/foreign/package-summary.html|publisher=Oracle Corporation}}</ref>

* They were implemented for the [[logic programming]] languages [[Prolog]]<ref>

{{Cite thesis |degree=Masters in Computer Science |title=Region-based memory management in Prolog |url=http://www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/00-09.pdf |last=Makholm |first=Henning |year=2000 |publisher=University of Copenhagen, Denmark |accessdate=20 February 2010 |url-status=dead |archive-url=https://web.archive.org/web/20110605004034/http://www.diku.dk/OLD/publikationer/tekniske.rapporter/rapporter/00-09.pdf |archive-date=5 June 2011 }}

Line 106 ⟶ 91:

{{cite conference |url=http://portal.acm.org/citation.cfm?id=362422.362434 |last=Makholm |first=Henning |title=A region-based memory manager for prolog |year=2000 |publisher=ACM |___location=New York, NY, USA |accessdate=22 February 2010 |book-title=ISMM '00: Proceedings of the 2nd international symposium on Memory management |pages=25&ndash;34 |isbn=1-58113-263-8|doi=10.1145/362422.362434}}

</ref> and [[Mercury programming language|Mercury]]<ref>

{{cite book |title=Static region analysis for Mercury |last1=Phan |first1=Quan |author-link1=Quan Phan |last2=Janssens |first2=Gerda |title=Logic Programming |series=Lecture Notes in Computer Science |author-link2=Gerda Janssens |year=2007 |publisher=Springer Berlin / Heidelberg |journal=Lecture Notes in Computer Science: Logic Programming |volume=4670/2007 |pages=317&ndash;332 |issn=1611-3349 |doi=10.1007/978-3-540-74610-2|series=Lecture Notes in Computer Science |isbn=978-3-540-74608-9 }}

</ref><ref>

{{cite conference |title=Runtime support for region-based memory management in Mercury |last1=Phan |first1=Quan |author-link1=Quan Phan |last2=Somogyi |first2=Zoltan |author-link2=Zoltan Somogyi |year=2008 |publisher=ACM |___location=New York, NY, USA |book-title=ISMM '08: Proceedings of the 7th international symposium on Memory management |pages=61&ndash;70 |isbn=978-1-60558-134-7|doi=10.1145/1375634.1375644 |url=http://dl.acm.org/citation.cfm?doid=1375634.1375644 |accessdate=15 April 2014|url-access=subscription }}

</ref> by extending Tofte and Talpin's region inference model to support backtracking and cuts.

* Region-based storage management is used throughout the [[parallel programming language]] [[ParaSail (programming language)|ParaSail]]. Due to the lack of explicit pointers in ParaSail,<ref>

{{Cite web |url=httphttps://parasail-programming-language.blogspot.com/2012/08/a-pointer-free-path-to-object-oriented.html|title=A Pointer-Free path to Object Oriented Parallel Programming |last1=Taft |first1=Tucker |year=2012 |work=ParaSail blog |accessdate=14 September 2012}}</ref> there is no need for reference counting.

== Disadvantages ==

Line 120 ⟶ 105:

== Hybrid methods ==

As mentioned above, RC uses a hybrid of regions and [[reference counting]], limiting the overhead of reference counting since references internal to regions don't require counts to be updated when they're modified. Similarly, some ''mark-region'' hybrid methods combine [[tracing garbage collection]] with regions; these function by dividing the heap into regions, performing a mark-sweep pass in which any regions containing live objects are marked, and then freeing any unmarked regions. These require continual defragmentation to remain effective.<ref>

{{cite conference |title=Immix: a mark-region garbage collector with space efficiency, fast collection, and mutator performance |last1=Blackburn |first1=Stephen M. |author-link1=Stephen M. Blackburn |last2=McKinley |first2=Kathryn S. |author-link2=Kathryn McKinley |year=2008 |publisher=ACM |___location=New York, NY, USA |book-title=PLDI '08: Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation |pages=22&ndash;32 |isbn=978-1-59593-860-2 |doi=10.1145/1375581.1375586 |url=http://dl.acm.org/citation.cfm?doid=1375581.1375586 |accessdate=15 April 2014|url-access=subscription }}

</ref>

== ExampleNotes ==

{{notelist}}

== References ==

Line 128 ⟶ 116:

{{Memory management navbox}}

[[Category:Articles with example C code]]

[[Category:Memory management]]