### Navigation

- index
- next |
- previous |
- Memory Pool System 1.111.0 documentation »
- Memory Management Glossary »

# Memory Management Glossary: F

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

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 can help application programmers to find bugs that would otherwise be difficult to reproduce and track down.

  Similar term

  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 indices 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 publication

  Wilson et al. (1995).

FIFO-ordered first fit

  The allocation policy that always uses the least-recently freed(1) 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 Wilson et al. (1995), 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.

file mapping

  See

  memory mapping.

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.

  In the MPS

  See Finalization.

finalized block

  In the MPS

  A block that has been registered for finalization using `mps_finalize()`, and which the MPS has determined is dead, but whose finalization message has not been discarded. See `mps_message_type_finalization()`.

first fit

  First fit is a sequential fit allocation mechanism.

  To quote Wilson et al. (1995):

  > 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(1). FIFO-ordered first fit puts blocks on the end of the free list when they are freed(1).

  See also

  address-ordered first fit, LIFO-ordered first fit, FIFO-ordered first fit, sequential fit, next fit, best fit, worst fit.

fix

  In the MPS

  To fix a reference from one block to another is to declare it to the MPS by calling `MPS_FIX1()` and `MPS_FIX2()` within a scan method. In a moving pool, fixing a reference may also update it to point to the new location of the block. See Scanning.

flip

  The instant in a two-space collector when the roles of the two semi-spaces are reversed. What was the tospace is now marked as fromspace and condemned. What was the fromspace becomes the site for all new allocations. Also used in a more general sense to mean the initiation of a new collection cycle.

  In a two-space collector, the flip occurs just before the fromspace is condemned and copying starts.

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

foreign code

  In the MPS

  From the point of view of the client program, foreign code is external code (not part of the client program, or the MPS), which is not aware of and does not co-operate with the MPS. The client program must take care when passing the address of a block in a moving pool to foreign code.

  The LO (Leaf Object) pool class is designed for this use case: blocks allocated from this pool do not move and are never protected, and so may be passed safely to foreign code.

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.

format method

  In the MPS

  One of the methods in an object format, defined by the client program in order to describe its objects to the MPS. May be a scan method, skip method, forward method, is-forwarded method, or padding method.

formatted object

  In the MPS

  An allocated block that belongs to an object format and may be scanned by the garbage collector. See Object formats.

forward method

  In the MPS

  A format method that is called by a moving pool when it has moved an object. The forward method replaces the old object with a forwarding marker that points to the new location of the object. See `mps_fmt_fwd_t`.

forwarding marker
forwarding object
forwarding pointer

  Some garbage collectors move reachable objects into another space. They leave a forwarding pointer, a special reference pointing to the new location, in the old location.

  Similar term

  broken heart.

  See also

  copying garbage collection, two-space collector.

  In the MPS

  The term forwarding object is used. This is a formatted object that has been replaced by a forwarding marker. One of three types of formatted objects, the other two being client objects and padding objects.

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 publication

  Johnstone & Wilson (1998).

frame

  See

  in-band header.

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.

  Opposite term

  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”.

  Opposite term

  allocated.

  See also

  free(1).

free(4)

  See

  unmapped.

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 publication

  Wilson et al. (1995).

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

  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

  See

  heap.

freestore

  See

  heap.

from space
fromspace

  Also known as

  old space, oldspace.

  In copying garbage collection, the space containing a mixture of live and dead objects, out of which the former are copied.

  Opposite term

  tospace.

function pointer

  In the C programming language, a pointer to an function, as distinct from a object pointer. The C programming language does not guarantee that function and object pointers are the same size, or that a pointer of one type can be cast to a pointer of the the other type without losing information (but on every mainstream C implementation, including all those supported by the MPS, they are in fact the same).

  Opposite term

  object pointer.

function record

  See

  activation record.

### Navigation

- index
- next |
- previous |
- Memory Pool System 1.111.0 documentation »
- Memory Management Glossary »