This is the entire Memory Management Glossary as one document and is designed to be suitable for printing; for online use, it is usually easier to access the glossary divided by letter. In this version, references to other entries are indicated «like this», and URLs are specified explicitly <URL:like this>.
Our aim is for these entries to be accurate, comprehensible, and useful, and also to have an entry for all common memory management terms. If you can't find the term you're looking for, if our definition doesn't help you, or if you'd like to suggest corrections or additions, please let us know via our feedback page.
For an explanation of the structure of the entries, and information on how to link to definitions, please see the glossary help page.
- absolute address
(for full details, see «physical address»)
Physical «addresses» are used to index into «physical memory(1)». On some systems, they are called absolute addresses.
- activation frame
(for full details, see «activation record»)
An activation or function record is a data structure, associated with the invocation of a function, procedure or control block that stores the variables, temporaries and fixed-sized data local to the block, and the information required to return to the invoking context. It is often stored on a «stack».
- activation record
(also known as function record, activation frame)
An activation or function record is a data structure, associated with the invocation of a function, procedure or control block that stores the variables, temporaries and fixed-sized data local to the block, and the information required to return to the invoking context. It is often stored on a «stack».
In a register-based hardware architecture, the current activation record is typically partially stored in registers.
«Closures» and «continuations» are specializations of activation records in support of particular language features of LISP, Scheme and related languages.
Relevance to memory management: The current activation record is part of the state of the «mutator», and is therefore a «root» to the «collector(2)». In languages that permit recursion, activation records have «dynamic extent». In languages that permit closures or continuations, activation records may have «indefinite extent». Although they may not be visible to the programmer, their «storage» must be managed by the language run-time support. Because they are usually not visible to the programmer, they may be a source of inexplicable memory overhead.
See also: «stack frame».
- activation stack
(for full details, see «control stack»)
A «stack» that stores «activation records», particularly subroutine return information, is known as a control stack.
- active
(for full details, see «live»)
«Memory(2)» or an «object» is live if the program will read from it in future. The term is often used more broadly to mean «reachable».
- address
An address is a specification of a «location» in an «address space».
An address is almost always represented as an unsigned integer stored in a single «machine word». The address is decoded by the hardware in order to access a location on a «physical memory(2)» device (such as a «RAM») or some «memory-mapped» resource.
A simplified view of addresses, address space, and locations on a 32-bit architecture
Similar terms: «pointer».
- address space
An address space is the set of possible «addresses».
It can also be considered to be a partial function from addresses to «locations».
Typically, addresses start at zero and run to 2^N-1, where N is the address width (for example, 15, 16, 24, 32, 64), which is usually the same as the width of the address bus. This may not be true for «segmented» architectures.
In modern systems, large parts of the whole address space may be reserved by the operating system or architecture, or not «mapped» at any given time. The mapped part of the address space may be discontiguous or sparse.
See also: «virtual address space»;
«physical address space».
- address translation cache
(for full details, see «TLB»)
The translation lookaside buffer or address translation cache is small piece of associative «memory(1)» within a processor which caches part of the translation from «virtual addresses» to «physical addresses».
- address-ordered first fit
The «allocation policy» that always uses the suitable «free block»
with the lowest address. One of the most common allocation policies in
use. Commonly implemented by «first fit» on a single address-ordered
«free block chain». Sometimes just called "first fit".
See also: «first fit»;
«LIFO-ordered first fit»;
«address-ordered first fit».
Related publications:
- aging space
In some «generational garbage collection» systems, when «generations» are divided into «buckets», the aging space is where «objects» which survive a «collection» stay until they are old enough to be «promoted».
Opposites: «creation space».
- algebraic data type
Algebraic data types aggregate or alternate a number of dissimilarly-typed objects. They are termed algebraic because they can be expressed as a sum-of-products: (a and b and c) or d.
Examples of algebraic data types include: structures, records, tuples, and unions.
Relevance to memory management: Algebraic data types are usually represented using a «heap». Because of their non-uniformity, algebraic data types are more difficult to «scan».
See also: «scalar data type»;
«vector data type»;
«heap».
- alignment
Alignment is a constraint on the «address» of an «object» in «memory(2)».
The constraint is usually that the object's address must be a multiple of a
power of two, 2^N, and therefore that the least significant N bits of
the address must be zero.
The bus hardware of many modern processors cannot access multi-«byte(2)»
objects at any memory address. Often «word»-sized objects must be aligned
to word boundaries, double-words to double-word boundaries,
double-floats to 8-byte boundaries, and so on. If a program attempts to access
an object that is incorrectly aligned, a «bus error» occurs.
Relevance to memory management: A memory manager must take care to «allocate» memory with an appropriate
alignment for the object that is going to be stored there.
Implementations of «malloc» have to allocate all «blocks» at the largest
alignment that the processor architecture requires.
Other reasons for aligning objects include using the least significant
bits of the address for a «tag».
Opposites: «unaligned».
See also: «natural alignment».
- alive
(for full details, see «live»)
«Memory(2)» or an «object» is live if the program will read from it in future. The term is often used more broadly to mean «reachable».
- allocate
(also known as cons(2))
Allocation is the process of assigning resources. When requested to by the program, an application «memory manager» or «allocator» allocates a «block» of «memory(2)» for the program to store its data in. Allocation is also known as consing, from «cons(1)».
When faced with a request for memory from the program, a memory manager must choose a suitable block and hand it over, or fail. The choices made by the memory manager at this point can have a significant effect on the future efficiency of the program.
Allocation is rarely a simple issue. For example, programs usually allocate «activation records» («automatic variables», and so on) for functions from a processor «stack» simply by subtracting a number from their stack «pointer». However, in a «virtual memory(1)» system, this may extend the stack onto a previously unused «page», in which case the operating system memory manager must carry out some quite complex operations in order to supply the program with «backing store» for the stack so that the program can continue.
Historical note: The term reserved was often used to mean "allocated".
Similar terms: «malloc».
Opposites: «free(1)».
See also: «constructor(1)».
Related publications:
- allocation mechanism
The algorithm by which an «allocator» chooses a «free block» from which to satisfy an allocation request. An allocation mechanism is the implementation of an «allocation policy».
A common mechanism is "«first fit» on an address-ordered «free block chain», with eager «coalescing»". This implements the «address-ordered first fit» policy, and commonly inherits that name, although there are many other mechanisms for implementing that policy (e.g. "leftmost fit on a balanced tree of free blocks ordered by address").
Related publications:
- allocation policy
(also known as placement policy)
The concrete policy used by an «allocator» for choosing a «free block» to satisfy an «allocation» request.
For instance, "always allocate from the largest free block" («worst fit») or "use the most recently freed block suitable" («LIFO-ordered first fit»).
Each allocation policy is motivated by an «allocation strategy» and implemented by an «allocation mechanism».
See also: «address-ordered first fit»;
«best fit».
Related publications:
- allocation strategy
The high-level design motivation or strategy, of an «allocator», which uses observations or theories about patterns of allocation requests to justify an «allocation policy».
For instance, "do not allow small long-lived «objects» to fragment large «free(3)» areas", "allocate consecutive objects close together", and so on. The allocation strategy motivates an «allocation policy», which is implemented by an «allocation mechanism».
Related publications:
- allocator
The term allocator is often used to refer to the «memory manager», usually when it is a simple manual one.
Similar terms: «memory manager».
See also: «allocation».
- ambiguous reference
(also known as unsure reference)
An ambiguous or unsure «reference» is a value that is potentially a reference, but the «collector(1)» cannot prove that it is.
The presence of ambiguous references in a «garbage-collected» system requires the use of «conservative garbage collection».
Opposites: «exact reference».
See also: «floating garbage».
- ambiguous root
An ambiguous root is a «root» containing «ambiguous references».
Opposites: «exact root».
See also: «conservative garbage collection».
- arena
The area of «memory(2)» used by «malloc» for allocation.
So named from a semi-mythical "malloc: corrupted arena" message supposedly emitted when some early versions became terminally confused.
See also: «brk».
- ATC
(for full details, see «TLB»)
The translation lookaside buffer or address translation cache is small piece of associative «memory(1)» within a processor which caches part of the translation from «virtual addresses» to «physical addresses».
- atomic object
(for full details, see «leaf object»)
A leaf object is an «object» that does not «reference» any other objects.
- automatic memory management
Automatic «memory management» is a general term for techniques that automatically «recycle» unused «memory(2)».
It is not possible, in general, to automatically determine which «objects» are still «live». Even if it didn't depend on future input, there can be no general algorithm to prove that an object is live (cf. the Halting Problem). However, effective approximations are possible.
In «tracing garbage collection», the approximation is that an object can't be live unless it is «reachable». In «reference counting», the approximation is that an object can't be live unless it is «referenced». Analysis of the program text can reveal where objects «die»; A notable technique in this vein is «region inference».
Hybrid algorithms are also possible.
Similar terms: «garbage collection».
Opposites: «manual memory management».
- automatic storage duration
In C, «objects» that are declared with automatic storage duration are «live» for the duration of a block of code.
In most implementations of C, objects with automatic storage duration are «allocated» on the «stack» when a function is entered, and «deallocated» when it returns.
Similar terms: «stack allocation»;
«dynamic extent».
Opposites: «static storage duration».
- backing store
Backing «store(2)» is typically part of a hard disk that is used by a «paging» or «swapping» system to store information not currently in «main memory». Backing store is slower and cheaper than main memory.
Other «storage» may, less commonly, be used in place of a hard disk (for instance, magnetic tape, floppy disk, or historically, magnetic drum).
In general, backing store may mean any locations used to store information when its preferred or natural location is otherwise being used -- for instance, memory used by a graphical interface to keep a copy of the contents of obscured windows.
Similar terms: «swap space».
- barrier(1)
A barrier is a block on reading from or writing to certain «memory(2)» «locations» by certain threads or processes.
Barriers can be implemented in either software or hardware. Software barriers involve additional instructions around «load» or «store(1)» operations, which would typically be added by a cooperative compiler. Hardware barriers don't require compiler support, and may be implemented on common operating systems by using «memory protection».
Relevance to memory management: Barriers are used for «incremental» or «concurrent» «garbage collection».
See also: «read barrier»;
«write barrier».
Related publications:
- barrier(2)
A memory barrier is an instruction on certain processor architectures that will ensure certain guarantees about the order of accesses to memory.
Some processor architectures, such as the Alpha AXP, make very few guarantees about the relative orders of «load» and «store(1)» operations in the instruction stream and the actual order of accesses to «main memory». These architectures will often have special instructions that make stronger guarantees.
For example Alpha AXP has the MB instruction which will:
Guarantee that all subsequent loads or stores will not access memory until after all previous loads and stores have accessed memory, as observed by other processors.
These instructions are vital for certain synchronization operations.
- base pointer
A base pointer is a «pointer» to the base or start of an «object».
This term is commonly used in opposition to «derived pointer».
Note that in A Proposal for Garbage-Collector-Safe C Compilation, Boehm and Chase define "base pointer" to be "any pointer value directly recognizable by the «collector(1)»", and this may well include «interior pointers».
Opposites: «derived pointer».
Related publications:
- best fit
The «allocation policy» that always allocates from the smallest
suitable «free block». Suitable «allocation mechanisms» include
«sequential fit» searching for a «perfect fit», «first fit» on a
size-ordered «free block chain», «segregated fits», and «indexed fits». Many «good fit» allocators are also described as «best fit».
In theory, best fit may exhibit bad «fragmentation», but in practice
this is not commonly observed.
See also: «allocation policy»;
«first fit»;
«sequential fit».
Related publications:
- BIBOP
(also known as big bag of pages)
BIBOP, or BIg Bag Of Pages, is a technique that encodes «object» type in the high-order bits of their «address», by using a lookup table that maps from those bits to a type.
Despite the name, the blocks involved need not be the size of a «page».
BIBOP requires storing only objects of the same type in a block, but this has the same advantages as «segregated fits» in general.
Historical note: This technique was invented for the PDP-10 MACLISP by JonL White and Stavros Macrakis. It was an advance on earlier techniques that divided the «address space» into contiguous blocks for each type.
Related publications:
- big bag of pages
(for full details, see «BIBOP»)
BIBOP, or BIg Bag Of Pages, is a technique that encodes «object» type in the high-order bits of their «address», by using a lookup table that maps from those bits to a type.
- binary buddies
The most common «buddy system» «allocation mechanism», in which all
block sizes are a power of two. Finding a block's buddy is then a
matter of flipping the appropriate bit in the block's address.
«Internal fragmentation» is usually high, because objects are often
not a good fit for power-of-two sized blocks.
See also: «buddy system»;
«allocation mechanism».
Related publications:
- bit-table
(for full details, see «bitmap»)
A table of bits.
- bitmap
(also known as bit-table)
A table of bits.
Relevance to memory management: Bitmaps are sometimes used to represent the marks in a «mark-sweep» collector, or the used memory in a «bitmapped fits» «allocator».
- bitmapped fit
A class of «allocation mechanisms» that use a «bitmap» to represent
the usage of the «heap». Each bit in the map corresponds to a
part of the heap, typically a «word», and is set if that
part is in use. Allocation is done by searching the bitmap
for a run of clear bits.
Bitmapped fit mechanisms have good «locality», as they avoid examining «in-band headers» when allocating.
See also: «allocation mechanism»;
«sequential fit»;
«indexed fit».
Related publications:
- black
In a «tri-color marking» scheme, black «objects» are objects that have been «scanned».
More precisely, black objects have been noted «reachable» and the «collector(2)» has finished with them and need not visit them again (for the purposes of «tracing»).
Opposites: «white»;
«gray».
- blacklisting, black-listing
A «conservative garbage collector» can be made more effective by blacklisting values which resemble «addresses» that may be «allocated» at in the future, but are known not to be «pointers» . This list is then used to avoid allocation at those addresses.
For example, such values can be gathered by scanning the «roots» before any «objects» have been allocated.
Related publications:
- block
Block is a vague term for an (often contiguous) area of «memory(1)». Often used to describe «memory(2)» «allocated» by an «allocator» such as «malloc».
- bounds error
(for full details, see «overwriting error»)
An overwriting or bounds error occurs when the programmer intends his program to write to a particular «block» of «memory(1)», but a program error causes the program to write outside the bounds of that block.
- boxed
Boxed «objects» are represented by a «pointer» to a «block» of «memory(2)» that contains the object data. Sometimes the pointer is «tagged» to distinguish it from an «unboxed» object, or to represent its type. Only the pointer is duplicated when the object is passed around, so updates to the object are reflected everywhere.
Opposites: «unboxed».
See also: «tag»;
«BIBOP».
Related publications:
- break-table
A break-table is a data structure used by a «mark-compact» collector to store the «relocation» information.
See also: «mark-compact».
- brk
brk is a UNIX® system call that sets the limit of the data segment. This limit is known as the break.
The C library implementation of «malloc» usually «allocates» «memory(2)» for the «heap» by extending the data segment with brk or «sbrk».
Unfortunately, most implementations of malloc never shrink the data segment, so the memory usage of a process never decreases. In most UNIX systems, the data segment resides immediately above the program code (text segment) in the «address space».
A simplified view of the address space of a UNIX process
- broken heart
«Copying garbage collectors» «move» «reachable» «objects» into another «semi-space». They leave a «forwarding pointer» in the old «location», pointing to the new. The object at the old location is known as a broken heart.
Similar terms: «forwarding pointer».
- bucket
In a «generational garbage collector», it is often desirable to divide «generations» by the age of the «object». These divisions are known as buckets.
See also: «generational garbage collection»;
«aging space»;
«creation space».
- buddy system
Buddy systems are a subclass of «strict segregated fit» «allocation mechanisms» which make «splitting» and «coalescing» fast by pairing
each block with a unique adjacent buddy block.
There is an array of «free lists», one for each allowable block
size. Allocation rounds up the requested size to an allowable size and
allocates from the corresponding free list. If the free list is empty,
a larger block is selected and split. A block may only be split into a
pair of buddies.
A block may only be coalesced with its buddy, and this is only
possible if the buddy has not been split into smaller blocks.
The advantage of buddy systems is that the buddy of a block being
freed can be quickly found by a simple address computation. The
disadvantage of buddy systems is that the restricted set of block
sizes leads to high «internal fragmentation», as does the limited
ability to coalesce.
Different sorts of buddy system are distinguished by the available
block sizes and the method of splitting. They include «binary buddies»
(the most common), «Fibonacci buddies», «weighted buddies», and
«double buddies».
See also: «allocation mechanism»;
«segregated free lists»;
«segregated fit»;
«strict segregated fit».
Related publications:
- buffer
A buffer is a large «block» of «memory(2)» from which blocks are «allocated» contiguously, as a simple technique for fast «allocation».
By keeping only a high-water mark (that is, a «pointer» to the start of unused memory), the buffer technique avoids expensive «in-band headers» and the searching of «free block chains». Buffers tend to, however, lead to «external fragmentation».
Related publications:
- bus error
Strictly speaking, a bus error is a fault on a hardware bus, such as when an invalid «address» is issued.
Generally, any hardware exception caused by a «memory(2)» access (for example, «loading» an «unaligned» «word») is termed a bus error. The term is often used more loosely as a synonym for any memory access error.
See also: «segmentation violation».
- byte(1)
A unit of storage measurement, equal to 8 bits.
It does not matter how the bits are arranged -- it is just a quantity.
This is the sense of byte used in the terms «kilobyte», «megabyte», «gigabyte», «terabyte», etc. The prefixes in these terms derive from the SI prefixes for powers of 1000, but since powers of two are much more common in binary computers, they are used to denote powers of 1024 (= 2^10).
See also: «word».
- byte(2)
A data type defined by a processor architecture.
For example, the smallest «addressable» storage «location» on the Intel x86
family is the 8-bit byte.
The PDP-10 has 36-bit «words», and defines "byte" to be a general sub-«word»
bit-field. (Compare this with «byte(3)».) On this machine it is commonplace
for characters to be packed four or five to a word using 9- or 7-bit bytes
respectively.
See also: «word».
- byte(3)
A contiguous set of bits used to represent a range of values compactly.
The number of bits in a byte is a measure of the information content of the
byte. An n-bit byte can represent 2^n distinct values.
Bytes may be packed into (or otherwise stored in bit-fields of) integers,
words, or other aligned values for space efficiency.
- byte(4)
A data type or storage unit defined by a programming language.
In ANSI/ISO C, "the unit of data storage large enough to hold the basic character set of the execution environment". In this sense, it is often used synonymously with the C type char. C defines sizeof(char) to be 1. Many architectures that run C programs equate this sense of byte and «byte(2)».
- cache(1)
(also known as memory cache, cache memory)
A processor's memory cache is a small piece of fast, but more expensive memory, usually «static memory(1)», used for copies of parts of «main memory». The cache is automatically used by the processor for fast access to any data currently «resident» there. Access to the cache typically takes only a few processor clock cycles, whereas access to «main memory» may take tens or even hundreds of cycles.
What part of main memory is resident in a cache, and the mechanisms by which it is kept consistent, are quite varied. See «cache policy».
Some systems have more than one level of cache. "level 1 cache" is the fastest, smallest «storage level», "level 2" the next fastest, and so on.
See also: «storage hierarchy»;
«cache(2)».
- cache(2)
A cache is any small, fast piece of «storage», used for copies of data that normally reside in a larger, slower piece of storage. The cache is used to speed up access to data «resident» in the slower storage.
In a typical cache, recently used data is «resident» in the cache (although the details of this depend on the «cache policy»). A «cache(1)» is the most common example of a cache(2).
See also: «storage hierarchy».
- cache memory
(for full details, see «cache(1)»)
A processor's memory cache is a small piece of fast, but more expensive memory, usually «static memory(1)», used for copies of parts of «main memory». The cache is automatically used by the processor for fast access to any data currently «resident» there. Access to the cache typically takes only a few processor clock cycles, whereas access to «main memory» may take tens or even hundreds of cycles.
- cache policy
Any «cache(3)» uses a cache policy to decide which data to store. A cache policy is an attempt to predict the future, so that the cache will provide swift responses to future requests.
Cache policy may be implemented in hardware, software, or a combination of both. Some systems allow programs to influence cache policy, by giving hints or directions about future use of data.
There are three main aspects of cache behavior which the cache policy can affect:
- Fetch policy
This determines which data is fetched into the cache, usually as a result of receiving a request for data that isn't cached.
- Eviction policy
This determines which data is discarded from the cache to provide space for newly fetched data.
- Write policy
This determines how and when modifications to cached data are synchronized with the underlying storage.
See also: «cache(1)»;
«cache(2)»;
«cache(3)».
Related publications:
- caching(3)
(also known as memoization, tabling)
Caching is a heuristic that stores answers to questions asked in the past in a cache or a table, in order that they may be more quickly answered in the future. This process is also called memoization and tabling (by the Prolog community).
A "look-ahead cache" attempts to store answers to questions that will be asked soon. A «cache(2)» is a common example of a cache(3).
- cactus stack
(also known as spaghetti stack)
A cactus stack is a «stack» with branches. When diagrammed, its shape resembles that of a saguaro cactus.
In languages that support «continuations», «activation records» can have «indefinite extent». One technique for implementing continuations is not to copy the activation records that are captured, rather to create a fork in the stack below the captured «stack frames», so that new frames appear as a parallel branch. Often the process of forking is done lazily, captured frames are only duplicated if they are modified.
- card
A card is a division of memory, all cards being of equal size (in a
particular area of discourse). A card is usually bigger than a «word»
and smaller than a «page». Cards are used in a technique called
«card-marking» whereby «dirty bits» (which record which portions of old
generations have been written into) are maintained for each card.
Often the use of cards will also entail the use of a «crossing map».
- card marking, card-marking
A technique for managing «pointer» «stores» into old «generations» (which in turn is used to track «inter-generational pointers»). Each generation is divided into a number of equal-sized «cards», and when a generation is written into, the particular card written to is recorded (often by using a «bit-table»). Subsequently, when «scanning» an older generation in order to collect a younger generation, only the recorded cards (in the old generation) need to be scanned.
See also: «generational garbage collection».
Related publications:
- cell
(for full details, see «object»)
In «memory management», we use the term object or cell to mean a contiguous «block» of «memory(2)» forming a single logical structure.
- Cheney collector
(also known as Cheney scan)
A Cheney collector uses the new «semi-space» of a «two space collector» as a
queue of objects remaining to be «scanned», thus eliminating the need for
recursion when «tracing» the «graph» of «objects».
See also: «two space collector».
Related publications:
- Cheney scan
(for full details, see «Cheney collector»)
A Cheney collector uses the new «semi-space» of a «two space collector» as a
queue of objects remaining to be «scanned», thus eliminating the need for
recursion when «tracing» the «graph» of «objects».
- closure
A closure is a function or procedure that is saved along with the current bindings from enclosing blocks for later invocation.
Some programming languages, such as Algol, permit nested blocks to access the local variables of enclosing blocks. Lisp-like languages further permit such an inner block (in particular a function or procedure) to be saved for later invocation. The act of saving such an inner block along with the current bindings of variables in the enclosing blocks that are referenced by the inner block, is called closing over or capturing those variables. The object created is termed a closure. A closure is invoked just like the function from which it was built, passing whatever parameters the function accepts, but when the function executes, the variables that belong to enclosing blocks will have the bindings that were in effect when the closure was created.
Relevance to memory management: A closure is typically implemented by saving both the function and any «activation records» that contain variables referenced by the function. The closure creates additional implicit «references» to the bindings closed over and hence must be accounted for in any memory management scheme.
The closure itself is an object that must be managed and may have either «dynamic extent» or «indefinite extent» depending on whether it is only used by inner blocks of the creating block or passed out of the creating block.
See also: «continuation».
- coalesce
Coalescing is the act of merging two adjacent «free blocks».
Coalescing reduces «external fragmentation», but is not totally effective.
Coalescing can be done as soon as blocks are freed, or it can be deferred until some time later (known as «deferred coalescing»), or it might not be done at all.
Dynamic Storage Allocation: A Survey and Critical Review has details about fragmentation, and which coalescing strategies are effective under what circumstances.
Related publications:
- collect
An «object» is collected when it is «reclaimed» by a «garbage collector».
Similar terms: «reclaim».
- collection
(for full details, see «collection cycle»)
A collection cycle is a single complete execution of a «tracing garbage collection» algorithm.
- collection cycle
(also known as collection)
A collection cycle is a single complete execution of a «tracing garbage collection» algorithm.
Each collection cycle includes (not necessarily in strict order) choosing a «condemned set»; «scanning» «roots» and «objects» that have not been condemned; «tracing» the object graph to find all condemned objects that are «reachable»; and «reclaiming» those that were not reachable.
In non-incremental garbage collection, the «mutator» pauses at the start of a collection cycle and cannot continue until it is complete. In «incremental» and «parallel» garbage collection, a collection cycle can be interleaved with, or simultaneous to, mutator activity.
- collector(1)
(for full details, see «garbage collector»)
A (garbage) collector is (an implementation of) a «garbage collection» algorithm.
- collector(2)
In a «garbage-collected» system, the part that executes the garbage collection code, which discovers unused «storage» and «reclaims» it.
For purposes of describing «incremental garbage collection», the system is divided into the «mutator» and the collector. These can be separate threads of computation, or interleaved within the same thread.
Historical note: This term is due to Dijkstra et al.
Opposites: «mutator».
Related publications:
- color, colour
In a «tri-color marking» scheme, each «node» has a one of three colors: «black», «white», or «gray». In a «treadmill», nodes may also be colored «off-white».
- committed
(for full details, see «mapped»)
A range of «virtual addresses» is said to be mapped (committed on Windows®) if there is «physical memory(2)» associated with the range.
- compactifying
(for full details, see «compaction»)
Compaction is the process of «moving» «live» «objects» to eliminate «dead» space between them. Some people call this compactifying, to distinguish it from techniques for compressing data structures.
- compaction
(also known as compactifying)
Compaction is the process of «moving» «live» «objects» to eliminate «dead» space between them. Some people call this compactifying, to distinguish it from techniques for compressing data structures.
Compaction is used to avoid «external fragmentation» and to increase «locality of reference».
- composite object
In the PostScript® language, composite objects are the «boxed» objects.
Unlike a «simple object», the main data (what PostScript calls the value) in a composite object are stored separately, in «VM(2)». Several composite objects can share the same value.
Similar terms: «boxed».
Opposites: «simple object».
- comprehensive
A «collector(1)» is comprehensive if all «garbage» (or, all «unreachable» «objects») is «reclaimed» in one «collection cycle».
See also: «garbage collection».
- concurrent garbage collection
(for full details, see «parallel garbage collection»)
A parallel or concurrent «collector(2)» executes simultaneously with the «mutator», usually on a multi-processor machine.
- condemned set
(for full details, see «threatened set»)
Condemned «objects» are those which are candidates for «recycling» within a «collection cycle».
- connected
«Objects» are connected if and only if one contains a «reference» to the other.
See also: «graph».
- cons(1)
In Lisp, cons is a primitive operation creating a list element (from English "CONStruct"). By extension, a cons is the element created.
Other links:
- cons(2)
(for full details, see «allocate»)
Allocation is the process of assigning resources. When requested to by the program, an application «memory manager» or «allocator» allocates a «block» of «memory(2)» for the program to store its data in. Allocation is also known as consing, from «cons(1)».
- conservative garbage collection
In conservative «garbage collection», the layout of «objects» and «roots» is not known, instead the «collector(1)» assumes that any field that looks like a «pointer» might be a «reference».
Conservative collectors can work with programs where information about the «memory(2)» layout is not available, because, for example, the language doesn't support «GC».
A conservative collector doesn't need to know the «format» of the objects, it just needs some idea of where the object boundaries are. It regards any field value that looks like a pointer to an object
(or, sometimes, into the middle of one), as preventing the «recycling» of that object. It can't «move» objects, because then the references to the moved objects would need to be updated, and such «ambiguous references» must not be modified, in case they weren't pointers after all. Therefore, conservative collectors are usually «mark-sweep collectors».
Because references are ambiguous, some objects may be retained despite being actually «unreachable». In practice, this happens rarely, and refinements such as «black-listing» can further reduce the odds.
Opposites: «exact garbage collection».
See also: «ambiguous root»;
«semi-conservative garbage collection»;
«interior pointer».
Related publications:
- constructor(1)
A constructor is a function or method that «allocates» and initializes an «object».
Opposites: «destructor(1)».
- constructor(2)
In C++, a constructor is a member function that is used to initialize a newly-«allocated» object.
The actual allocation of «memory(2)» is performed by operator new or the compiler (for «static» and «stack allocation»), and the new «block» is then passed to the appropriate constructor.
See also: «destructor(2)».
- continuation
A continuation is the data required to restore an execution context after invocation of another context, typically as a subroutine.
Relevance to memory management: If continuations can be represented as first-class objects, as in Scheme, the execution contexts can no longer be stored on a «stack», instead, (at least some) «activation records» have to be «heap-allocated».
See also: «closure».
- control stack
(also known as activation stack, execution stack)
A «stack» that stores «activation records», particularly subroutine return information, is known as a control stack.
Typically the control stack is supported and used by the hardware architecture and the operating system, limiting the types and sizes of «objects» that can be stored on it. Often, only one type of object, a «stack frame», is permitted, and the layout of that is defined by the hardware architecture.
Relevance to memory management: Theoretically, a control stack is simply an array of activation records, and hence just another object managed by the «memory manager». In practice, the control stack is central to the performance of the hardware architecture and may require special treatment. In particular, it may not be accessible as ordinary «memory(2)», or it may have its own «cache(2)» with specific updating requirements.
Similar terms: «stack».
See also: «data stack».
- copying garbage collection
(also known as scavenging garbage collection)
Copying garbage collection is a kind of «tracing garbage collection» that operates by «relocating» «reachable» «objects» (this is sometimes called scavenging) and then «reclaiming» objects that are left behind, which must be «unreachable» and therefore «dead».
A copying garbage collection relies on being able to find and correct all «references» to copied objects.
Copying garbage collection
Similar terms: «moving».
See also: «broken heart»;
«forwarding pointer»;
«two-space collector».
- core
A historical synonym for «main memory», deriving from the cores or ferrite rings which were once the main technology used to implement main memory.
Similar terms: «main memory».
- creation space
In «generational garbage collection», when «generations» are divided into «buckets», the creation space is where new «objects» are created in each generation.
This term is sometimes used as a synonym for «nursery space».
Opposites: «aging space».
See also: «generational garbage collection».
- crossing map
Where «memory(2)» has already been divided into some fixed-sized unit (for example, «pages» or «cards»), a crossing map records where «objects» lie across the boundaries of the fixed-sized units. In other words, which fixed-sized units do not start with the beginning of an object.
A system which implements «remembered sets» by «page-marking» or «card-marking» needs to scan all the «pointers» in the page or card. If the system can not «scan» partial objects (or requires information in the object «header» in order to scan a partial object), a crossing map is necessary to find the beginning of the first object in the unit.
Relevance to memory management: In a sense, a crossing map is an optimization of «tagged architecture». It represents the minimum information necessary to determine how to interpret any word of memory.
- cyclic data structure
A data structure is cyclic if some of its «references» form a loop; that is, there's an «object» that can be reached by following references from itself.
- dangling pointer
A dangling «pointer» is a surviving «reference» to an «object» that no longer exists at that «address»
In «manual memory management», dangling pointers typically arise from one of:
Dangling pointers can occur under «automatic memory management», because of a «garbage collection» bug -- such as premature collection, or «moving» without updating all «references» -- but this is much rarer because «GC» code is usually a single common core of reused code.
- data stack
A «stack» used to manage the storage of «stack-allocated» «objects», other than «activation records», often under program control.
Because of the limitations that may be imposed on the «control stack», or to support stack-like semantics for certain data structures, some language implementations manage additional data stacks in software for storing objects that have «dynamic extent» but that do not fit within the constraints of the control stack.
See also: «control stack».
- dead
An «object» is dead if it is not «live»; that is, when the «mutator» cannot reach any state in which it accesses the object.
It is not possible, in general, for «garbage collectors» to determine exactly which «objects» are dead and which are live. Instead, they use some approximation to detect objects that are provably dead, such as those that are «unreachable».
Opposites: «live».
See also: «garbage»;
«undead»;
«free(3)».
- deallocate
(for full details, see «free(1)»)
In «manual memory management», to free or deallocate an «object» is to tell the «memory manager» that it is no longer needed. The «memory(1)» may then be «recycled» by being used for subsequent «allocation», or by being returned to the operating system.
- deferred coalescing
Deferred coalescing is a policy which «coalesces» «free blocks» some time after the blocks are freed, as opposed to coalescing free blocks immediately as they are freed.
Adjacent free blocks can be coalesced to form larger free blocks; deferred coalescing is a catch-all for policies which perform this coalescing sometime after the blocks were freed.
Given this rather flexible definition there are a number of choices for when to coalesce: as the «free list» is traversed during allocation, when the allocation cannot be satisfied from the free list, periodically, and so on. In addition there are choices to be made regarding how much coalescing to perform at any one time.
- deferred reference counting
Deferred «reference counting» reduces the cost of maintaining reference counts by avoiding adjustments when the «reference» is stored on the «stack».
On many systems, the majority of stores are made into local variables, which are kept on the stack. Deferred reference counting leaves those out and counts only references stored in «heap» objects. This requires compiler support, but can lead to substantial performance improvements.
«Objects» cannot be «reclaimed» as soon as their reference count becomes zero, because there might still be references to them from the stack. Such objects are added to a «zero count table» (ZCT) instead. If a reference to an object with a count of zero is stored into the heap, then the object is removed from the ZCT. Periodically the stack is «scanned», and any objects in the ZCT which were not referenced from the stack are reclaimed.
Deferred reference counting has been used successfully with several languages, notably Smalltalk. However, since it fails to collect objects with «cyclic» references, it is often used alongside a «tracing garbage collector».
Related publications:
- derived pointer
(for full details, see «interior pointer»)
An interior pointer is a pointer to «memory(2)» occupied by an «object» which does not point to the start location. Also called a derived pointer when it's derived from a «base pointer».
- destructor(1)
A destructor is a function or a method that performs the explicit «deallocation» of an «object». It may also perform clean-up actions.
Opposites: «constructor(1)».
- destructor(2)
In C++, a destructor is a member function that is used to clean up when an object is being «deallocated».
When an object is being destroyed (by delete or automatically), the appropriate destructor is called, and then the actual deallocation of «memory(2)» is performed by operator delete or the run-time system (for «static» and «stack allocation»).
See also: «constructor(2)».
- DGC
(for full details, see «distributed garbage collection»)
Distributed garbage collection is «garbage collection» in a system where «objects» might not reside in the same «address space» or even on the same machine.
- direct method
Direct methods of «automatic memory management» maintain information about the «liveness» of each «object», detecting «garbage» directly.
Such bits of information, e.g., «reference counts», are typically stored within the objects themselves.
Direct «garbage collection» can allow «memory(2)» to be «reclaimed» as soon as it becomes «unreachable». However, the stored information must be updated as the «graph» of objects changes; this may be an expensive operation, especially in «distributed garbage collection» where it can lead to intensive communication between processors, and make garbage collection less robust to network failures.
Opposites: «indirect method».
Related publications:
- dirty bit
A dirty bit is a flag indicating that a «page» (or similar) has been written to since it was last examined.
Dirty bits are used by «caches(2)» to determine which pages must be written out, and by garbage collectors in conjunction with «write barriers».
- distributed garbage collection
(also known as DGC)
Distributed garbage collection is «garbage collection» in a system where «objects» might not reside in the same «address space» or even on the same machine.
Distributed garbage collection is difficult to achieve in widely-distributed systems (over wide-area networks) because of the costs of synchronization and communication between processes. These costs are particularly high for a «tracing garbage collector», so other techniques, including «weighted reference counting», are commonly used instead.
- double buddies
A «buddy system» «allocation mechanism» using a pair of «binary buddy» systems with staggered size classes.
One system is a pure binary buddy, with powers-of-two classes (2, 4, 8,...). The other uses some fixed multiple of powers-of-two (e.g., 3, 6, 12, ...). This resembles «weighted buddies», but the two buddy systems are treated independently: blocks cannot be «split» or «coalesced» from one to the other.
Related publications:
- double free
A double free is when an attempt is made to «free(1)» a «memory(2)» «block» that has already been freed.
This usually occurs in «manual memory management» when two parts of a program believe they are responsible for the management of the same block.
Many manual «memory managers» have great trouble with double frees, because they cannot cheaply determine that «deallocated» blocks were already free. Instead, they corrupt their «free block chain», which leads to mysterious problems when the same block is subsequently «allocated».
See also: «premature free».
- doubleword
(also known as longword)
A doubleword is a unit of memory consisting of two adjacent «words». In digital's Alpha architecture, it's called a longword.
Historical note: On the Intel® 80386, 80486. and Pentium® processors, the doubleword of 32 bits is actually the natural word size, but the term word is still used for the 16-bit unit, as it was on earlier processors of this series.
See also: «quadword».
- DRAM
(for full details, see «dynamic memory»)
Dynamic memory, or dynamic RAM (DRAM, pronounced "dee ram"), is a type of «RAM».
- dynamic allocation
(for full details, see «heap allocation»)
Heap allocation or dynamic allocation means run-time «allocation» and «deallocation» of «storage» in arbitrary order.
- dynamic extent
An «object» has dynamic «extent» if its «lifetime» is bounded by the execution of a function or some other block construct.
Objects of dynamic extent are usually «stack-allocated».
Similar terms: «automatic storage duration».
Opposites: «indefinite extent».
- dynamic memory
(also known as dynamic RAM, DRAM)
Dynamic memory, or dynamic RAM (DRAM, pronounced "dee ram"), is a type of «RAM».
Dynamic RAM requires periodic refreshing to avoid losing its contents (as opposed to «static memory(1)», the contents of which are preserved without any need for refreshing). The refreshing is performed by additional "refresh hardware" usually external to the dynamic RAM package itself, sometimes by the main CPU. Dynamic RAM is cheap and compact and is the choice for large amounts of relatively fast RAM, such as the «main memory» of PCs. Dynamic RAM often comes packaged in SIMMs or DIMMs.
See also: «static memory(1)»;
«SDRAM».
- dynamic RAM
(for full details, see «dynamic memory»)
Dynamic memory, or dynamic RAM (DRAM, pronounced "dee ram"), is a type of «RAM».
- edge
In a «graph», an edge is a connection between two «nodes».
In a directed graph (digraph), edges have a direction; otherwise the start and end nodes are interchangeable.
By convention, two directed edges between the same two nodes, but in different directions, are depicted as a bi-directional edge.
Typically an edge represents some relation between nodes.
Relevance to memory management: In memory management, edges normally represent the fact that an «object» holds a «reference» to another object.
See also: «graph».
- entry table(1)
An entry table is a table of «references» into a set of «objects» used to indirect references from the outside.
The Lieberman-Hewitt «collector(1)» represented references from older «generations» to younger ones by indirect pointers through an entry table in the younger generation that contained the actual «address» of the young object. This is fairly expensive without special hardware; other «generational» collectors generally use «remembered sets».
See also: «generational garbage collection»;
«exit table».
Related publications:
- entry table(2)
An entry table is an implementation of a «remembered set», where, for a given «generation», there is a list of «objects» in older generations which contain «references» into that generation.
One could also store the actual «locations» of the references, which would save time when «scanning», but incur other costs.
Similar terms: «remembered set».
See also: «generational garbage collection»;
«exit table».
- exact garbage collection
(also known as precise garbage collection, type-accurate garbage collection)
«Garbage collection» is exact (or precise) if it deals only with «exact references».
An exact «collector(1)» needs to know the «format» of the «objects» and the «roots», so that it can tell which fields are references.
Opposites: «conservative garbage collection».
- exact reference
(also known as precise reference, sure reference)
An exact or precise or sure reference is a value the «collector(1)» knows is a «reference».
This is the usual sort of reference. The term is used to draw a contrast with «ambiguous reference».
Opposites: «ambiguous reference».
- exact root
(also known as precise root)
An exact or precise root is a «root» that contains only «exact references».
Opposites: «ambiguous root».
See also: «exact reference».
- exact segregated fit
A «segregated fit» «allocation mechanism» which has a separate «free list» for each possible block size. The array of free lists may be
represented sparsely. Large blocks may be treated separately.
See also: «segregated fit»;
«segregated free list»;
«allocation mechanism».
Related publications:
- execution stack
(for full details, see «control stack»)
A «stack» that stores «activation records», particularly subroutine return information, is known as a control stack.
- exit table
An exit table is a table of all «references» from a set of «objects» to objects outside the set.
See also: «entry table(1)»;
«entry table(2)».
Related publications:
- extent
(for full details, see «lifetime»)
The lifetime or extent of an «object» is the time for which the object is «live».
- external fragmentation
External «fragmentation» is the inability to use «memory(1)» because «free(3)» memory is divided into many small «blocks».
If «live» «objects» are scattered, the free blocks cannot be «coalesced», and hence no large blocks can be «allocated».
Common solutions to external fragmentation include:
See also: «internal fragmentation».
Related publications:
- fencepost, fence post
A fencepost is spare «memory(1)» between «allocated» «blocks» for checking purposes.
Some «memory management» systems leave spare memory between allocated blocks and store special values in it. If a checking routine finds that these memory «locations» have been modified, this probably indicates an «overwriting error» in the application that was allocated the adjacent block.
Such checking is extremely useful in a memory manager, because it can help application programmers to find bugs that would otherwise be difficult to reproduce and track down.
Similar terms: «in-band header».
- fencepost error, fence post error
The term fencepost error refers to errors arising from the fact that, to enclose n consecutive intervals, you need n+1 end-points, from the number of posts required to support fence rails.
An example of a fencepost error would be, in C:
void f(void)
{
int i;
int a[10];
for(i = 0; i <= 10; i++)
a[i] = 0;
}
because the declaration int a[10]; creates an array of ten integers, with index from 0 to 9, but the for loop index i runs from 0 to 10.
- Fibonacci buddies
A common «buddy system» «allocation mechanism», in which block sizes
form a Fibonacci series (each block size is the sum of the two
previous sizes). Each block can therefore be «split» to form two blocks
of valid sizes, and the sizes are more closely spaced than in «binary buddies». However, if the same size is allocated repeatedly,
performance may suffer as the remainder blocks may have to be split
again (or become fragments).
See also: «buddy system»;
«allocation mechanism».
Related publications:
- FIFO-ordered first fit
The «allocation policy» that always uses the least-recently «freed»
suitable «free block». Commonly implemented by adding freed blocks to
the end of a «free block chain», and then using «first fit» allocation
on this chain. «free(1)» can be very quick, depending on the «coalescing»
policy.
According to Dynamic Storage Allocation: A Survey and Critical Review, this policy controls fragmentation quite well, better than «LIFO-ordered first fit» and as well as «address-ordered first fit» in some cases, although «locality» may be worse.
See also: «first fit»;
«LIFO-ordered first fit»;
«address-ordered first fit»;
«allocation policy».
Related publications:
- file mapping
(for full details, see «memory mapping»)
Memory mapping is the technique of making a part of the «address space» appear to contain an "object", such as a file or device, so that ordinary «memory(2)» accesses act on that object.
- finalization
(also known as termination)
In «garbage-collected» languages, it is often necessary to perform actions on some «objects» after they are no longer in use and before their «memory(2)» can be «recycled». These actions are known as finalization or termination.
A common use of finalization is to release resources when the corresponding "proxy" object dies. For example, an open file might be represented by a stream object. When this object has been proven «dead» by the «collector(1)», it is certain that the file is no longer in use by the program, and it can and should be closed before the stream is recycled.
Note that finalization is not, in general, guaranteed to be prompt, and this can cause problems if it is used to manage scarce operating system resources such as file descriptors.
Many object-oriented languages provide support for finalization, for example, Cedar, Java, Perl 5, and Smalltalk.
The term finalization is sometimes used to refer to the use of «destructors(1)», for example in Ada.
- first fit
First fit is a «sequential fit» «allocation mechanism».
To quote Dynamic Storage Allocation: A Survey and Critical Review:
First fit simply searches the «free list» from the beginning, and uses the first
«free block» large enough to satisfy the request. If the block is
larger than necessary, it is split and the remainder is put on the free
list.
The first fit mechanism provides a class of first fit «allocation policies», depending on the order in which the free list is
stored. «Address-ordered first fit» stores the list in order of
(usually increasing) address. «LIFO-ordered first fit» puts blocks on
the front of the free list when they are «freed». «FIFO-ordered first fit» puts blocks on the end of the free list when they are «freed».
See also: «address-ordered first fit»;
«LIFO-ordered first fit»;
«FIFO-ordered first fit»;
«sequential fit»;
«next fit»;
«best fit»;
«worst fit».
Related publications:
- flip
The instant in a «two-space collector» when the roles of the two «semi-spaces» are reversed. What was the new semi-space is now marked as old and «condemned». What was the old semi-space becomes the site for all new «allocations». Also used in a more general sense to mean the initiation of a new «collection cycle».
- floating garbage
Floating garbage is «garbage» that is not «recycled» promptly due to some approximation or optimization in the «garbage collector».
Floating garbage results from conservatively estimating an «object» that is really «unreachable» to be «reachable» for the purposes of a particular «collection cycle». Using estimates can have considerable performance benefits but also result in higher «memory(2)» consumption.
Typical estimates that cause floating garbage are:
- Every register or «activation frame» slot holds a reachable value: this is not always true, as objects stored in dead registers or slots may be otherwise unreachable. This estimate can simplify the compiler as well as the interface between the compiler and the garbage collector.
- Every object in a «remembered set» is reachable: this is not always true, because remembered objects can have become unreachable since they were added to the remembered set. This estimate allows remembered sets to be effective; the alternative -- determining whether each remembered object is reachable -- is equivalent to a full garbage collection.
- Anything that looks like a «reference» is one: this is not generally true, because random data can have the same bit pattern as a pointer. «Conservative garbage collectors» use this estimate.
- Any object referenced from another is reachable: this is not generally true, because garbage can reference other garbage. «Reference counting» collectors use this estimate, resulting in their not being able to reclaim self-referential structures.
- Any object reached during collection remains live until the next collection: this may not be true when the garbage collector runs interleaved with the mutator, as do «incremental» and «concurrent» collectors.
A more subtle kind of floating garbage is an unreachable data structure that spans multiple regions that are never «condemned» together.
- format
A format describes the representation of an «object»; that is, how the object is laid out in memory.
A format usually specifies where the fields of the objects are located and what their type is.
Relevance to memory management: If formats are provided by a language or the application program, «exact garbage collection» can be used, because the «collector(1)» can determine which fields are «references».
See also: «conservative garbage collection».
- forwarding pointer
Some «garbage collectors» «move» «reachable» «objects» into another space. They leave a «forwarding pointer» -- that is, a special «reference» pointing to the new location -- in the old «location», .
Similar terms: «broken heart».
See also: «copying garbage collection»;
«two space collector».
- fragmentation
Fragmentation is the inability to use «memory(1)» because of the arrangement of memory already in use.
It is usually divided into «external fragmentation» and «internal fragmentation».
Related publications:
- frame
(for full details, see «in-band header»)
Some «memory managers» «allocate» a fixed amount more than is necessary for each «block» and use it to store information such as the size of the block or a «tag». This extra memory is known as an in-band header or a frame
- free(1)
(also known as deallocate)
In «manual memory management», to free or deallocate an «object» is to tell the «memory manager» that it is no longer needed. The «memory(1)» may then be «recycled» by being used for subsequent «allocation», or by being returned to the operating system.
Opposites: «allocate».
See also: «free(2)»;
«destructor(1)».
- free(2)
In C, the system function used for explicit «deallocation» is called free.
- free(3)
«Memory(2)» is free if it is not currently «allocated».
Historical note: The term available was commonly used to mean "free".
Opposites: «allocated».
See also: «allocate»;
«free(1)».
- free(4)
(for full details, see «unmapped»)
A range of «virtual addresses» is said to be unmapped (free on Windows®) if there is no «physical memory(2)» associated with the range.
- free block
A single contiguous area of «memory(2)» available to satisfy an «allocation» request.
For the purpose of discussing «allocation mechanisms», two adjacent free blocks are not considered to be a single free block, until they are «coalesced». Free blocks may be «split».
See also: «allocation mechanism»;
«free list».
Related publications:
- free block chain
Some systems store the «free list» as a linked list, or chain.
Usually the links are stored within the «free(3)» «blocks». This means that all «allocated» blocks must be large enough to store these, and implies a minimum size.
Sometimes, the free block chain is ordered by «address». This makes «coalescence» considerably cheaper, but «deallocation» more expensive.
See also: «free list».