GenericFreeList (Jikes RVM API)

java.lang.Object
- org.mmtk.utility.BaseGenericFreeList
- - org.mmtk.utility.GenericFreeList

public final class GenericFreeList
extends BaseGenericFreeList

This is a very simple, generic malloc-free allocator. It works abstractly, in "units", which the user may associate with some other allocatable resource (e.g. heap blocks). The user issues requests for N units and the allocator returns the index of the first of a contiguous set of N units or fails, returning -1. The user frees the block of N units by calling free() with the index of the first unit as the argument.

Properties/Constraints:

The allocator consumes one word per allocatable unit (plus a fixed overhead of about 128 words).
The allocator can only deal with MAX_UNITS units (see below for the value).

The basic data structure used by the algorithm is a large table, with one word per allocatable unit. Each word is used in a number of different ways, some combination of "undefined" (32), "free/used" (1), "multi/single" (1), "prev" (15), "next" (15) & "size" (15) where field sizes in bits are in parenthesis.

                       +-+-+-----------+-----------+
                       |f|m|    prev   | next/size |
                       +-+-+-----------+-----------+

   - single free unit: "free", "single", "prev", "next"
   - single used unit: "used", "single"
    - contiguous free units
     . first unit: "free", "multi", "prev", "next"
     . second unit: "free", "multi", "size"
     . last unit: "free", "multi", "size"
    - contiguous used units
     . first unit: "used", "multi", "prev", "next"
     . second unit: "used", "multi", "size"
     . last unit: "used", "multi", "size"
    - any other unit: undefined

                       +-+-+-----------+-----------+
   top sentinel        |0|0|    tail   |   head    |  [-1]
                       +-+-+-----------+-----------+
                                     ....
            /--------  +-+-+-----------+-----------+
            |          |1|1|   prev    |   next    |  [j]
            |          +-+-+-----------+-----------+
            |          |1|1|           |   size    |  [j+1]
         free multi    +-+-+-----------+-----------+
         unit block    |              ...          |  ...
            |          +-+-+-----------+-----------+
            |          |1|1|           |   size    |
           >--------  +-+-+-----------+-----------+
   single free unit    |1|0|   prev    |   next    |
           >--------  +-+-+-----------+-----------+
   single used unit    |0|0|                       |
           >--------  +-+-+-----------------------+
            |          |0|1|                       |
            |          +-+-+-----------+-----------+
            |          |0|1|           |   size    |
         used multi    +-+-+-----------+-----------+
         unit block    |              ...          |
            |          +-+-+-----------+-----------+
            |          |0|1|           |   size    |
            \--------  +-+-+-----------+-----------+
                                     ....
                       +-+-+-----------------------+
   bottom sentinel     |0|0|                       |  [N]
                       +-+-+-----------------------+

The sentinels serve as guards against out of range coalescing because they both appear as "used" blocks and so will never coalesce. The top sentinel also serves as the head and tail of the doubly linked list of free blocks.

Field Summary

Fields
Modifier and Type	Field and Description
`private static int`	`COALESC_MASK`
`private static int`	`FREE_MASK`
`static int`	`MAX_UNITS`
`private static int`	`MULTI_MASK`
`private static int`	`NEXT_MASK`
`private GenericFreeList`	`parent`
`private static int`	`PREV_MASK`
`private static int`	`SIZE_MASK`
`private int[]`	`table`
`private static int`	`TOTAL_BITS`
`private static int`	`UNIT_BITS`

Fields inherited from class org.mmtk.utility.BaseGenericFreeList
DEBUG, FAILURE, head, heads, MAX_HEADS

Constructor Summary

Constructors
Constructor and Description
`GenericFreeList(GenericFreeList parent, int ordinal)` Constructor
`GenericFreeList(int units)` Constructor
`GenericFreeList(int units, int grain)` Constructor
`GenericFreeList(int units, int grain, int heads)` Constructor

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`clearUncoalescable(int unit)` Clear the uncoalescable bit associated with this unit.
`protected boolean`	`getFree(int unit)` Establish whether a lump of units is free
`(package private) int`	`getHeads()`
`private int`	`getHiEntry(int unit)`
`protected int`	`getLeft(int unit)` Get the lump to the "left" of the current lump (i.e.
`private int`	`getLoEntry(int unit)` Get the contents of an entry
`protected int`	`getNext(int unit)` Get the next lump in the doubly linked free list
`protected int`	`getPrev(int unit)` Get the previous lump in the doubly linked free list
`protected int`	`getSize(int unit)` Get the size of a lump of units
`(package private) int[]`	`getTable()`
`boolean`	`isCoalescable(int unit)` Return true if this unit may be coalesced with the unit below it.
`void`	`resizeFreeList()` Resize the free list for a child free list.
`void`	`resizeFreeList(int units, int grain)` Resize the free list for a parent free list.
`protected void`	`setFree(int unit, boolean isFree)` Set the "free" flag for a lump of units (both the first and last units in the lump are set.
`private void`	`setHiEntry(int unit, int value)`
`private void`	`setLoEntry(int unit, int value)` Set the contents of an entry
`protected void`	`setNext(int unit, int next)` Set the next lump in the doubly linked free list
`protected void`	`setPrev(int unit, int prev)` Set the previous lump in the doubly linked free list
`protected void`	`setSentinel(int unit)` Initialize a unit as a sentinel
`protected void`	`setSize(int unit, int size)` Set the size of lump of units
`void`	`setUncoalescable(int unit)` Set the uncoalescable bit associated with this unit.

Methods inherited from class org.mmtk.utility.BaseGenericFreeList
alloc, alloc, couldAlloc, dbgPrintFree, free, free, initializeHeap, initializeHeap, size

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - TOTAL_BITS
```
private static final int TOTAL_BITS
```
    See Also:
    
    Constant Field Values
  - UNIT_BITS
```
private static final int UNIT_BITS
```
    See Also:
    
    Constant Field Values
  - MAX_UNITS
```
public static final int MAX_UNITS
```
    See Also:
    
    Constant Field Values
  - NEXT_MASK
```
private static final int NEXT_MASK
```
    See Also:
    
    Constant Field Values
  - PREV_MASK
```
private static final int PREV_MASK
```
    See Also:
    
    Constant Field Values
  - FREE_MASK
```
private static final int FREE_MASK
```
    See Also:
    
    Constant Field Values
  - MULTI_MASK
```
private static final int MULTI_MASK
```
    See Also:
    
    Constant Field Values
  - COALESC_MASK
```
private static final int COALESC_MASK
```
    See Also:
    
    Constant Field Values
  - SIZE_MASK
```
private static final int SIZE_MASK
```
    See Also:
    
    Constant Field Values
  - table
```
private int[] table
```
  - parent
```
private final GenericFreeList parent
```
- Constructor Detail
  - GenericFreeList
```
public GenericFreeList(int units)
```
    Constructor
    
    Parameters:
    
    units - The number of allocatable units for this free list
  - GenericFreeList
```
public GenericFreeList(int units,
                       int grain)
```
    Constructor
    
    Parameters:
    
    units - The number of allocatable units for this free list
    
    grain - Units are allocated such that they will never cross this granularity boundary
  - GenericFreeList
```
public GenericFreeList(int units,
                       int grain,
                       int heads)
```
    Constructor
    
    Parameters:
    
    units - The number of allocatable units for this free list
    
    grain - Units are allocated such that they will never cross this granularity boundary
    
    heads - The number of free lists which will share this instance
  - GenericFreeList
```
public GenericFreeList(GenericFreeList parent,
                       int ordinal)
```
    Constructor
    
    Parameters:
    
    parent - The parent, owning the data structures this instance will share
    
    ordinal - The ordinal number of this child
- Method Detail
  - resizeFreeList
```
public void resizeFreeList(int units,
                           int grain)
```
    Resize the free list for a parent free list. This must not be called dynamically (ie not after bootstrap).
    
    Parameters:
    
    units - The number of allocatable units for this free list
    
    grain - Units are allocated such that they will never cross this granularity boundary
  - resizeFreeList
```
public void resizeFreeList()
```
    Resize the free list for a child free list. This must not be called dynamically (ie not after bootstrap).
  - getTable
```
int[] getTable()
```
  - getHeads
```
int getHeads()
```
  - setSentinel
```
protected void setSentinel(int unit)
```
    Initialize a unit as a sentinel
    
    Specified by:
    
    setSentinel in class BaseGenericFreeList
    
    Parameters:
    
    unit - The unit to be initialized
  - getSize
```
protected int getSize(int unit)
```
    Get the size of a lump of units
    
    Specified by:
    
    getSize in class BaseGenericFreeList
    
    Parameters:
    
    unit - The first unit in the lump of units
    
    Returns:
    
    The size of the lump of units
  - setSize
```
protected void setSize(int unit,
                       int size)
```
    Set the size of lump of units
    
    Specified by:
    
    setSize in class BaseGenericFreeList
    
    Parameters:
    
    unit - The first unit in the lump of units
    
    size - The size of the lump of units
  - getFree
```
protected boolean getFree(int unit)
```
    Establish whether a lump of units is free
    
    Specified by:
    
    getFree in class BaseGenericFreeList
    
    Parameters:
    
    unit - The first or last unit in the lump
    
    Returns:
    
    true if the lump is free
  - setFree
```
protected void setFree(int unit,
                       boolean isFree)
```
    Set the "free" flag for a lump of units (both the first and last units in the lump are set.
    
    Specified by:
    
    setFree in class BaseGenericFreeList
    
    Parameters:
    
    unit - The first unit in the lump
    
    isFree - true if the lump is to be marked as free
  - getNext
```
protected int getNext(int unit)
```
    Get the next lump in the doubly linked free list
    
    Specified by:
    
    getNext in class BaseGenericFreeList
    
    Parameters:
    
    unit - The index of the first unit in the current lump
    
    Returns:
    
    The index of the first unit of the next lump of units in the list
  - setNext
```
protected void setNext(int unit,
                       int next)
```
    Set the next lump in the doubly linked free list
    
    Specified by:
    
    setNext in class BaseGenericFreeList
    
    Parameters:
    
    unit - The index of the first unit in the lump to be set
    
    next - The value to be set.
  - getPrev
```
protected int getPrev(int unit)
```
    Get the previous lump in the doubly linked free list
    
    Specified by:
    
    getPrev in class BaseGenericFreeList
    
    Parameters:
    
    unit - The index of the first unit in the current lump
    
    Returns:
    
    The index of the first unit of the previous lump of units in the list
  - setPrev
```
protected void setPrev(int unit,
                       int prev)
```
    Set the previous lump in the doubly linked free list
    
    Specified by:
    
    setPrev in class BaseGenericFreeList
    
    Parameters:
    
    unit - The index of the first unit in the lump to be set
    
    prev - The value to be set.
  - setUncoalescable
```
public void setUncoalescable(int unit)
```
    Set the uncoalescable bit associated with this unit. This ensures this unit cannot be coalesced with units below it.
    
    Parameters:
    
    unit - The unit whose uncoalescable bit is to be set
  - clearUncoalescable
```
public void clearUncoalescable(int unit)
```
    Clear the uncoalescable bit associated with this unit. This allows this unit to be coalesced with units below it.
    
    Parameters:
    
    unit - The unit whose uncoalescable bit is to be cleared
  - isCoalescable
```
public boolean isCoalescable(int unit)
```
    Return true if this unit may be coalesced with the unit below it.
    
    Specified by:
    
    isCoalescable in class BaseGenericFreeList
    
    Parameters:
    
    unit - The unit in question
    
    Returns:
    
    true if this unit may be coalesced with the unit below it.
  - getLeft
```
protected int getLeft(int unit)
```
    Get the lump to the "left" of the current lump (i.e. "above" it)
    
    Specified by:
    
    getLeft in class BaseGenericFreeList
    
    Parameters:
    
    unit - The index of the first unit in the lump in question
    
    Returns:
    
    The index of the first unit in the lump to the "left"/"above" the lump in question.
  - getLoEntry
```
private int getLoEntry(int unit)
```
    Get the contents of an entry
    
    Parameters:
    
    unit - The index of the unit
    
    Returns:
    
    The contents of the unit
  - getHiEntry
```
private int getHiEntry(int unit)
```
  - setLoEntry
```
private void setLoEntry(int unit,
                        int value)
```
    Set the contents of an entry
    
    Parameters:
    
    unit - The index of the unit
    
    value - The contents of the unit
  - setHiEntry
```
private void setHiEntry(int unit,
                        int value)
```

Class GenericFreeList

Field Summary

Fields inherited from class org.mmtk.utility.BaseGenericFreeList

Constructor Summary

Method Summary

Methods inherited from class org.mmtk.utility.BaseGenericFreeList

Methods inherited from class java.lang.Object

Field Detail

TOTAL_BITS

UNIT_BITS

MAX_UNITS

NEXT_MASK

PREV_MASK

FREE_MASK

MULTI_MASK

COALESC_MASK

SIZE_MASK

table

parent

Constructor Detail

GenericFreeList

GenericFreeList

GenericFreeList

GenericFreeList

Method Detail

resizeFreeList

resizeFreeList

getTable

getHeads

setSentinel

getSize

setSize

getFree

setFree

getNext

setNext

getPrev

setPrev

setUncoalescable

clearUncoalescable

isCoalescable

getLeft

getLoEntry

getHiEntry

setLoEntry

setHiEntry