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 BaseGenericFreeList

java.lang.Object
  extended by org.mmtk.utility.BaseGenericFreeList
All Implemented Interfaces:
Constants
Direct Known Subclasses:
GenericFreeList
abstract class BaseGenericFreeList
extends Object
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
protected static boolean DEBUG
           
static int FAILURE
           
protected  int head
           
protected  int heads
           
protected static int 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
BaseGenericFreeList()
           
 
Method Summary
private  void addToFree(int unit)
          Add a lump of units to the free list
 int alloc(int size)
          Allocate size units.
 int alloc(int size, int unit)
          Allocate size units.
private  int alloc(int size, int unit, int unitSize)
          Allocate size units.
private  void coalesce(int start, int end)
          Coalesce two or three contiguous lumps of units, removing start and end lumps from the free list as necessary.
 boolean couldAlloc(int size)
          Would an allocation of size units succeed?
(package private)  void dbgPrintFree()
          Print the free list (for debugging purposes)
 int free(int unit)
          Free a previously allocated contiguous lump of units.
 int free(int unit, boolean returnCoalescedSize)
          Free a previously allocated contiguous lump of units.
(package private) abstract  boolean getFree(int unit)
           
(package private) abstract  int getLeft(int unit)
           
(package private) abstract  int getNext(int unit)
           
(package private) abstract  int getPrev(int unit)
           
private  int getRight(int unit)
          Get the lump to the "right" of the current lump (i.e.
(package private) abstract  int getSize(int unit)
           
protected  void initializeHeap(int units)
          Initialize a new heap.
protected  void initializeHeap(int units, int grain)
          Initialize a new heap.
(package private) abstract  boolean isCoalescable(int unit)
           
private  void removeFromFree(int unit)
          Remove a lump of units from the free list
(package private) abstract  void setFree(int unit, boolean isFree)
           
(package private) abstract  void setNext(int unit, int next)
           
(package private) abstract  void setPrev(int unit, int prev)
           
(package private) abstract  void setSentinel(int unit)
           
(package private) abstract  void setSize(int unit, int size)
           
 int size(int unit)
          Return the size of the specified lump of units
private  void split(int unit, int size)
          Reduce a lump of units to size, freeing any excess.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEBUG

protected static final boolean DEBUG
See Also:
Constant Field Values

FAILURE

public static final int FAILURE
See Also:
Constant Field Values

MAX_HEADS

protected static final int MAX_HEADS
See Also:
Constant Field Values

heads

protected int heads

head

protected int head
Constructor Detail

BaseGenericFreeList

BaseGenericFreeList()
Method Detail

alloc

public final int alloc(int size)
Allocate size units. Return the unit ID

Parameters:
size - The number of units to be allocated
Returns:
The index of the first of the size contiguous units, or -1 if the request can't be satisfied

couldAlloc

public final boolean couldAlloc(int size)
Would an allocation of size units succeed?

Parameters:
size - The number of units to test for
Returns:
True if such a request could be satisfied.

alloc

public final int alloc(int size,
                       int unit)
Allocate size units. Return the unit ID

Parameters:
size - The number of units to be allocated
Returns:
The index of the first of the size contiguous units, or -1 if the request can't be satisfied

alloc

private int alloc(int size,
                  int unit,
                  int unitSize)
Allocate size units. Return the unit ID

Parameters:
size - The number of units to be allocated
Returns:
The index of the first of the size contiguous units, or -1 if the request can't be satisfied

free

public final int free(int unit)
Free a previously allocated contiguous lump of units.

Parameters:
unit - The index of the first unit.
Returns:
return the size of the unit which was freed.

free

public final int free(int unit,
                      boolean returnCoalescedSize)
Free a previously allocated contiguous lump of units.

Parameters:
unit - The index of the first unit.
returnCoalescedSize - if true, return the coalesced size
Returns:
The number of units freed. if returnCoalescedSize is false, return the size of the unit which was freed. Otherwise return the size of the unit now available (the coalesced size)

size

public final int size(int unit)
Return the size of the specified lump of units

Parameters:
unit - The index of the first unit in the lump.
Returns:
The size of the lump, in units.

initializeHeap

protected final void initializeHeap(int units)
Initialize a new heap. Fabricate a free list entry containing everything

Parameters:
units - The number of units in the heap

initializeHeap

protected final void initializeHeap(int units,
                                    int grain)
Initialize a new heap. Fabricate a free list entry containing everything

Parameters:
units - The number of units in the heap

split

private void split(int unit,
                   int size)
Reduce a lump of units to size, freeing any excess.

Parameters:
unit - The index of the first unit
size - The size of the first part

coalesce

private void coalesce(int start,
                      int end)
Coalesce two or three contiguous lumps of units, removing start and end lumps from the free list as necessary.

Parameters:
start - The index of the start of the first lump
end - The index of the start of the last lump

addToFree

private void addToFree(int unit)
Add a lump of units to the free list

Parameters:
unit - The first unit in the lump of units to be added

removeFromFree

private void removeFromFree(int unit)
Remove a lump of units from the free list

Parameters:
unit - The first unit in the lump of units to be removed

getRight

private int getRight(int unit)
Get the lump to the "right" of the current lump (i.e. "below" it)

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 "right"/"below" the lump in question.

dbgPrintFree

void dbgPrintFree()
Print the free list (for debugging purposes)

setSentinel

abstract void setSentinel(int unit)

getSize

abstract int getSize(int unit)

setSize

abstract void setSize(int unit,
                      int size)

getFree

abstract boolean getFree(int unit)

setFree

abstract void setFree(int unit,
                      boolean isFree)

getNext

abstract int getNext(int unit)

setNext

abstract void setNext(int unit,
                      int next)

getPrev

abstract int getPrev(int unit)

setPrev

abstract void setPrev(int unit,
                      int prev)

getLeft

abstract int getLeft(int unit)

isCoalescable

abstract boolean isCoalescable(int unit)
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