Memory Management Glossary: O

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

object

Also known as

cell.

In memory management, we use the term object or cell to mean a contiguous block of memory⁽²⁾ forming a single logical structure.

Objects are the units of allocation, deallocation, etc. No connection to an object-oriented system is implied.

In the MPS

The MPS documentation generally reserves the term object for formatted objects. For units of allocation in general, it uses the term block.

object format

In the MPS

A data structure provided by the client program which describes the format of objects allocated in a pool. The MPS uses the format methods to find references in an object, replace an object with padding, replace an object with a forwarding marker, and other essential garbage collection tasks. See Object formats.

object pointer

In the C programming language, a pointer to an object, as distinct from a function pointer. The C programming language guarantees that you can cast any object pointer to void * and back without losing information.

Opposite term

function pointer.

off-white

Also known as

ecru.

In a treadmill garbage collector, the color off-white is used to describe objects which are free⁽³⁾. Baker (1992c) used the term ecru.

Opposite terms

white, gray, black.

See also

treadmill, color.

old space
oldspace

See

fromspace.

one-bit reference count

The one-bit reference count is a heuristic mechanism that lets a program test, at low cost, whether an object is dead.

The one-bit reference count is a special case of the limited-field reference count. A single bit in an object, called the MRB (Multiple Reference Bit), is cleared when the object is allocated. Whenever another reference to the object is created, the bit is set. Thus, MRB=0 indicates that there is exactly one reference to the object, and MRB=1 indicates that there may be more than one reference to the object.

The MRB can be stored in the reference rather than in the object; doing so reduces the number of memory accesses due to MRB checking and setting. When a reference is copied, the copy’s MRB is set. If the MRB in the old reference is 0, it also needs to be set. Setting the MRB in the old reference requires that the program knows the location the old reference came from, and that it can prove that location has not since been overwritten with other data.

The one-bit reference count is used by a compiler to augment an object lifetime analysis. When compile-time analysis predicts that a particular object may be dead (typically because the variable that references the object is dead), the compiler can generate code that will check the object’s MRB at run-time. If the MRB is 0, then the object is dead.

Using a one-bit reference count does have a cost: the MRB uses space that could sometimes be put to other use, and the MRB must be set every time the number of references to the object increases. The one-bit reference count is cheaper than other kinds of reference counting, however, since the space cost is only one bit and the reference count is not adjusted when references are destroyed.

Historical note

The one-bit reference count was suggested by Friedman & Wise (1977). Storing the MRB in the reference was suggested by Stoye, Clarke, and Norman (1984).

Related publication

Jones et al. (2012).

opaque type

In the MPS

In the MPS interface, an opaque type is a pointer to an incomplete structure type. The client programs must not rely on the details of its implementation. For example, the type mps_arena_t is an alias for struct mps_arena_s *, but the implementation of struct mps_arena_s is not public. See Interface conventions.

Opposite terms

derived type, transparent type.

out parameter

A function parameter that points to a location for the caller to receive data from the function.

Opposite term

in parameter.

In the MPS

Out parameters are given names ending with _o. See Interface conventions.

out-of-band header

In some memory managers, each allocated block has additional information (such as the size of the block or a tag) stored in a separate block; this is called an out-of-band header.

Opposite term

in-band header.

overcommit

In some circumstances, although a range of virtual addresses has been mapped as far as the user program is concerned, the physical storage might not be allocated until it is accessed. This is called overcommitting.

Overcommitting shares swap space resources more flexibly, especially when crude suballocators are involved, but it can lead to an out-of-resource error during a memory⁽²⁾ access; few environments deal with this situation gracefully.

Unix systems such as IRIX and AIX can do this on sbrk and mmap calls.

overwriting error

Also known as

bounds error.

An overwriting or bounds error occurs when the programmer intends his program to write to a particular block of memory⁽¹⁾, but a program error causes the program to write outside the bounds of that block.

See also

fencepost.