The Memory Management Glossary
F

 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.


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:

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.

free list, free-list

The free list is the set of free blocks.

Originally this term meant the single linked list of all free blocks, but as allocation mechanisms have become more varied, it has become more generic, and now may be implemented as a tree or other data structure rather than a linked list. If the implementation actually is a linked list of free blocks, this is called a free block chain to distinguish it from the abstract term.

There may be several free lists, classed by size or other characteristic. For instance, segregated free list systems classify free lists by block size.

See also: free block; free block chain.

free store (for full details, see heap)

The heap or free store is the memory(2) area managed by dynamic allocation.

freestore (for full details, see heap)

The heap or free store is the memory(2) area managed by dynamic allocation.

function record (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.

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