BaseGenericFreeList (Jikes RVM API)

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

Direct Known Subclasses:: GenericFreeList

abstract class BaseGenericFreeList
extends Object

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

protected static boolean DEBUG

static int FAILURE

protected int head

protected int heads

protected static int MAX_HEADS

Fields
Modifier and Type	Field and Description
`protected static boolean`	`DEBUG`
`static int`	`FAILURE`
`protected int`	`head`
`protected int`	`heads`
`protected static int`	`MAX_HEADS`

Constructor Summary

Constructors
Constructor and Description

BaseGenericFreeList()

Constructors
Constructor and Description
`BaseGenericFreeList()`

Method Summary

All Methods Instance Methods Abstract Methods Concrete Methods
Modifier and Type	Method and Description
`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
    
    unit - TODO needs documentation
    
    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
    
    unit - TODO needs documentation
    
    unitSize - TODO needs documentation
    
    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
    
    grain - TODO needs documentation
  - 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)
```

Class BaseGenericFreeList

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

DEBUG

FAILURE

MAX_HEADS

heads

head

Constructor Detail

BaseGenericFreeList

Method Detail

alloc

couldAlloc

alloc

alloc

free

free

size

initializeHeap

initializeHeap

split

coalesce

addToFree

removeFromFree

getRight

dbgPrintFree

setSentinel

getSize

setSize

getFree

setFree

getNext

setNext

getPrev

setPrev

getLeft

isCoalescable