Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

org.mmtk.utility
Class GenericFreeList

java.lang.Object
  extended by org.mmtk.utility.BaseGenericFreeList
      extended by org.mmtk.utility.GenericFreeList
All Implemented Interfaces:
Constants
public final class GenericFreeList
extends BaseGenericFreeList
implements Constants

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 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
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
 
Fields inherited from interface org.mmtk.utility.Constants
ALIGNMENT_VALUE, ARRAY_ELEMENT, BITS_IN_ADDRESS, BITS_IN_BYTE, BITS_IN_CHAR, BITS_IN_INT, BITS_IN_PAGE, BITS_IN_SHORT, BITS_IN_WORD, BYTES_IN_ADDRESS, BYTES_IN_BYTE, BYTES_IN_CHAR, BYTES_IN_INT, BYTES_IN_KBYTE, BYTES_IN_MBYTE, BYTES_IN_PAGE, BYTES_IN_SHORT, BYTES_IN_WORD, CARD_MASK, CARD_META_PAGES_PER_REGION, INSTANCE_FIELD, LOG_BITS_IN_ADDRESS, LOG_BITS_IN_BYTE, LOG_BITS_IN_CHAR, LOG_BITS_IN_INT, LOG_BITS_IN_PAGE, LOG_BITS_IN_SHORT, LOG_BITS_IN_WORD, LOG_BYTES_IN_ADDRESS, LOG_BYTES_IN_ADDRESS_SPACE, LOG_BYTES_IN_BYTE, LOG_BYTES_IN_CHAR, LOG_BYTES_IN_INT, LOG_BYTES_IN_KBYTE, LOG_BYTES_IN_MBYTE, LOG_BYTES_IN_PAGE, LOG_BYTES_IN_SHORT, LOG_BYTES_IN_WORD, LOG_CARD_BYTES, LOG_CARD_GRAIN, LOG_CARD_META_BYTES, LOG_CARD_META_PAGES, LOG_CARD_META_SIZE, LOG_CARD_UNITS, LOG_MIN_ALIGNMENT, MAX_ALIGNMENT, MAX_BYTES_PADDING, MAX_INT, MIN_ALIGNMENT, MIN_INT, SUPPORT_CARD_SCANNING
 
Constructor Summary
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
 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)
Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD