The Memory Management Glossary
A

 Contents | News | Glossary | FAQ | Articles | Bibliography | Links | Feedback

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help

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
Diagram: 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.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z - Help