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.
In memory management, we use the term object or cell to mean a contiguous block of memory(2) forming a single logical structure.
Objects are the units of allocation, deallocation, etc. No connection to an object-oriented system is implied.
In a treadmill garbage collector, the color off-white is used to describe objects which are free(3).
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 and Wise The One-Bit Reference Count. Storing the MRB in the reference was suggested by Stoye, Clarke, and Norman Some Practical Methods for Rapid Combinator Reduction.
Related publications:
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.
Opposites: in-band header.
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(2) access; few environments deal with this situation gracefully.
UNIX® systems such as IRIX® and AIXTM can do this on sbrk and mmap calls.
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.
See also: fencepost.