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.alloc
Class BumpPointer

java.lang.Object
  extended by org.mmtk.utility.alloc.Allocator
      extended by org.mmtk.utility.alloc.BumpPointer
All Implemented Interfaces:
Constants
Direct Known Subclasses:
CopyLocal, ImmortalLocal, MarkCompactLocal
public class BumpPointer
extends Allocator
implements Constants

This class implements a bump pointer allocator that allows linearly scanning through the allocated objects. In order to achieve this in the face of parallelism it maintains a header at a region (1 or more blocks) granularity.

Intra-block allocation is fast, requiring only a load, addition comparison and store. If a block boundary is encountered the allocator will request more memory (virtual and actual).

In the current implementation the scanned objects maintain affinity with the thread that allocated the objects in the region. In the future it is anticipated that subclasses should be allowed to choose to improve load balancing during the parallel scan.

Each region is laid out as follows: 


  +-------------+-------------+-------------+---------------
  | Region  End | Next Region |  Data  End  | Data -->
 +-------------+-------------+-------------+---------------
The minimum region size is 32768 bytes, so the 3 or 4 word overhead is less than 0.05% of all space.

An intended enhancement is to facilitate a reallocation operation where a second cursor is maintained over earlier regions (and at the limit a lower location in the same region). This would be accompianied with an alternative slow path that would allow reuse of empty regions.

This class relies on the supporting virtual machine implementing the getNextObject and related operations.

Field Summary
protected  boolean allowScanning
          linear scanning is permitted if true
protected static Word BLOCK_MASK
           
private static int BLOCK_SIZE
           
protected  Address cursor
          insertion point
protected static Offset DATA_END_OFFSET
           
protected static Offset DATA_START_OFFSET
           
protected  Address initialRegion
          first contiguous region
private  Address internalLimit
          current internal slow-path sentinel for bump pointer
private  Address limit
          current external slow-path sentinel for bump pointer
protected static int LOG_BLOCK_SIZE
           
private static int LOG_DEFAULT_STEP_SIZE
           
protected static Offset MAX_DATA_START_OFFSET
           
static int MINIMUM_DATA_SIZE
           
protected static Offset NEXT_REGION_OFFSET
           
protected  Address region
          current contiguous region
protected static Offset REGION_LIMIT_OFFSET
           
private static int SIZE_OF_TWO_X86_CACHE_LINES_IN_BYTES
           
protected  Space space
          space this bump pointer is associated with
private static int STEP_SIZE
           
private static boolean VERBOSE
           
 
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
protected BumpPointer(Space space, boolean allowScanning)
          Constructor.
 
Method Summary
 Address alloc(int bytes, int align, int offset)
          Allocate space for a new object.
private  Address allocSlow(Address start, Address end, int align, int offset)
          Internal allocation slow path.
protected  Address allocSlowOnce(int bytes, int align, int offset)
          External allocation slow path (called by superclass when slow path is actually taken.
static void checkRegionMetadata(Address region)
          Sanity check a region header
static void clearNextRegion(Address region)
          Clear the next region pointer in the linked-list of regions
private  Address consumeNextRegion(Address nextRegion, int bytes, int align, int offset)
          A bump pointer chunk/region has been consumed but the contiguous region is available, so consume it and then return the address of the start of a memory region satisfying the outstanding allocation request.
private  void createCardAnchor(Address card, Address start, int bytes)
          Given an allocation which starts a new card, create a record of where the start of the object is relative to the start of the card.
 void gcspyGatherData(LinearSpaceDriver driver)
          Gather data for GCspy.
 void gcspyGatherData(LinearSpaceDriver driver, Space scanSpace)
          Gather data for GCspy.
private static Address getCard(Address address)
          Return the start of the card corresponding to a given address.
private static Address getCardMetaData(Address card)
          Return the address of the metadata for a card, given the address of the card.
 Address getCursor()
           
static Address getDataEnd(Address region)
           
static Address getDataStart(Address region)
          The first offset in a region after the header
static Address getNextRegion(Address region)
          The next region in the linked-list of regions
static Address getRegionLimit(Address region)
          Return the end address of the given region.
 Space getSpace()
          Return the space this allocator is currently bound to.
static boolean isRegionAligned(Address region)
           
 void linearScan(LinearScan scanner)
          Perform a linear scan through the objects allocated by this bump pointer.
protected  Extent maximumRegionSize()
          Maximum size of a single region.
 void rebind(Space space)
          Re-associate this bump pointer with a different space.
 void reset()
          Reset the allocator.
protected  void reusePages(int pages)
          Some pages are about to be re-used to satisfy a slow path request.
private  void scanRegion(LinearScan scanner, Address start)
          Perform a linear scan through a single contiguous region
static void setDataEnd(Address region, Address endAddress)
           
static void setNextRegion(Address region, Address nextRegion)
          Set the next region in the linked-list of regions
static void setRegionLimit(Address region, Address limit)
          Store the limit value at the end of the region.
 void show()
          Print out the status of the allocator (for debugging)
protected  void updateLimit(Address newLimit, Address start, int bytes)
          Update the limit pointer.
private  void updateMetaData(Address start, Extent size, int bytes)
          Update the metadata to reflect the addition of a new region.
 
Methods inherited from class org.mmtk.utility.alloc.Allocator
alignAllocation, alignAllocation, alignAllocationNoFill, allocSlow, allocSlowInline, determineCollectionAttempts, fillAlignmentGap, getMaximumAlignedSize, getMaximumAlignedSize
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

LOG_DEFAULT_STEP_SIZE

private static final int LOG_DEFAULT_STEP_SIZE
See Also:
Constant Field Values

STEP_SIZE

private static final int STEP_SIZE
See Also:
Constant Field Values

LOG_BLOCK_SIZE

protected static final int LOG_BLOCK_SIZE

BLOCK_MASK

protected static final Word BLOCK_MASK

BLOCK_SIZE

private static final int BLOCK_SIZE

REGION_LIMIT_OFFSET

protected static final Offset REGION_LIMIT_OFFSET

NEXT_REGION_OFFSET

protected static final Offset NEXT_REGION_OFFSET

DATA_END_OFFSET

protected static final Offset DATA_END_OFFSET

DATA_START_OFFSET

protected static final Offset DATA_START_OFFSET

MAX_DATA_START_OFFSET

protected static final Offset MAX_DATA_START_OFFSET

MINIMUM_DATA_SIZE

public static final int MINIMUM_DATA_SIZE

SIZE_OF_TWO_X86_CACHE_LINES_IN_BYTES

private static final int SIZE_OF_TWO_X86_CACHE_LINES_IN_BYTES
See Also:
Constant Field Values

VERBOSE

private static final boolean VERBOSE
See Also:
Constant Field Values

cursor

protected Address cursor
insertion point

internalLimit

private Address internalLimit
current internal slow-path sentinel for bump pointer

limit

private Address limit
current external slow-path sentinel for bump pointer

space

protected Space space
space this bump pointer is associated with

initialRegion

protected Address initialRegion
first contiguous region

allowScanning

protected final boolean allowScanning
linear scanning is permitted if true

region

protected Address region
current contiguous region

Constructor Detail

BumpPointer

protected BumpPointer(Space space,
                      boolean allowScanning)
Constructor.

Parameters:
space - The space to bump point into.
allowScanning - Allow linear scanning of this region of memory.
Method Detail

reset

public final void reset()
Reset the allocator. Note that this does not reset the space. This is must be done by the caller.

rebind

public final void rebind(Space space)
Re-associate this bump pointer with a different space. Also reset the bump pointer so that it will use the new space on the next call to alloc.

Parameters:
space - The space to associate the bump pointer with.

alloc

public final Address alloc(int bytes,
                           int align,
                           int offset)
Allocate space for a new object. This is frequently executed code and the coding is deliberately sensitive to the optimizing compiler. After changing this, always check the IR/MC that is generated.

Parameters:
bytes - The number of bytes allocated
align - The requested alignment
offset - The offset from the alignment
Returns:
The address of the first byte of the allocated region

allocSlow

private Address allocSlow(Address start,
                          Address end,
                          int align,
                          int offset)
Internal allocation slow path. This is called whenever the bump pointer reaches the internal limit. The code is forced out of line. If required we perform an external slow path take, which we inline into this method since this is already out of line.

Parameters:
start - The start address for the pending allocation
end - The end address for the pending allocation
align - The requested alignment
offset - The offset from the alignment
Returns:
The address of the first byte of the allocated region

createCardAnchor

private void createCardAnchor(Address card,
                              Address start,
                              int bytes)
Given an allocation which starts a new card, create a record of where the start of the object is relative to the start of the card.

Parameters:
card - An address that lies within the card to be marked
start - The address of an object which creates a new card.
bytes - The size of the pending allocation in bytes (used for debugging)

getCard

private static Address getCard(Address address)
Return the start of the card corresponding to a given address.

Parameters:
address - The address for which the card start is required
Returns:
The start of the card containing the address

getCardMetaData

private static Address getCardMetaData(Address card)
Return the address of the metadata for a card, given the address of the card.

Parameters:
card - The address of some card
Returns:
The address of the metadata associated with that card

allocSlowOnce

protected final Address allocSlowOnce(int bytes,
                                      int align,
                                      int offset)
External allocation slow path (called by superclass when slow path is actually taken. This is necessary (rather than a direct call from the fast path) because of the possibility of a thread switch and corresponding re-association of bump pointers to kernel threads.

Specified by:
allocSlowOnce in class Allocator
Parameters:
bytes - The number of bytes allocated
offset - The offset from the alignment
align - The requested alignment
Returns:
The address of the first byte of the allocated region or zero on failure

updateLimit

protected final void updateLimit(Address newLimit,
                                 Address start,
                                 int bytes)
Update the limit pointer. As a side effect update the internal limit pointer appropriately.

Parameters:
newLimit - The new value for the limit pointer
start - The start of the region to be allocated into
bytes - The size of the pending allocation (if any).

consumeNextRegion

private Address consumeNextRegion(Address nextRegion,
                                  int bytes,
                                  int align,
                                  int offset)
A bump pointer chunk/region has been consumed but the contiguous region is available, so consume it and then return the address of the start of a memory region satisfying the outstanding allocation request. This is relevant when re-using memory, as in a mark-compact collector.

Parameters:
nextRegion - The region to be consumed
bytes - The number of bytes allocated
align - The requested alignment
offset - The offset from the alignment
Returns:
The address of the first byte of the allocated region or zero on failure

getDataStart

public static Address getDataStart(Address region)
The first offset in a region after the header

Parameters:
region - The region
Returns:
The lowest address at which data can be stored

getNextRegion

public static Address getNextRegion(Address region)
The next region in the linked-list of regions

Parameters:
region - The region
Returns:
The next region in the list

setNextRegion

public static void setNextRegion(Address region,
                                 Address nextRegion)
Set the next region in the linked-list of regions

Parameters:
region - The region
nextRegion - the next region in the list

clearNextRegion

public static void clearNextRegion(Address region)
Clear the next region pointer in the linked-list of regions

Parameters:
region - The region

getDataEnd

public static Address getDataEnd(Address region)
Parameters:
region - The bump-pointer region
Returns:
The DATA_END address from the region header

setDataEnd

public static void setDataEnd(Address region,
                              Address endAddress)
Parameters:
region - The bump-pointer region
endAddress - The new DATA_END address from the region header

getRegionLimit

public static Address getRegionLimit(Address region)
Return the end address of the given region.

Parameters:
region - The region.
Returns:
the allocation limit of the region.

setRegionLimit

public static void setRegionLimit(Address region,
                                  Address limit)
Store the limit value at the end of the region.

isRegionAligned

public static boolean isRegionAligned(Address region)
Parameters:
region - The region.
Returns:
true if the address is region-aligned

checkRegionMetadata

public static void checkRegionMetadata(Address region)
Sanity check a region header

Parameters:
region - Region to check

updateMetaData

private void updateMetaData(Address start,
                            Extent size,
                            int bytes)
Update the metadata to reflect the addition of a new region.

Parameters:
start - The start of the new region
size - The size of the new region (rounded up to block-alignment)

gcspyGatherData

public void gcspyGatherData(LinearSpaceDriver driver)
Gather data for GCspy.

This method calls the drivers linear scanner to scan through the objects allocated by this bump pointer.

Parameters:
driver - The GCspy driver for this space.

gcspyGatherData

public void gcspyGatherData(LinearSpaceDriver driver,
                            Space scanSpace)
Gather data for GCspy.

This method calls the drivers linear scanner to scan through the objects allocated by this bump pointer.

Parameters:
driver - The GCspy driver for this space.
scanSpace - The space to scan

linearScan

public final void linearScan(LinearScan scanner)
Perform a linear scan through the objects allocated by this bump pointer.

Parameters:
scanner - The scan object to delegate scanning to.

scanRegion

private void scanRegion(LinearScan scanner,
                        Address start)
Perform a linear scan through a single contiguous region

Parameters:
scanner - The scan object to delegate to.
start - The start of this region

reusePages

protected void reusePages(int pages)
Some pages are about to be re-used to satisfy a slow path request.

Parameters:
pages - The number of pages.

maximumRegionSize

protected Extent maximumRegionSize()
Maximum size of a single region. Important for children that implement load balancing or increments based on region size.

Returns:
the maximum region size

getCursor

public final Address getCursor()
Returns:
the current cursor value

getSpace

public final Space getSpace()
Description copied from class: Allocator
Return the space this allocator is currently bound to.

Specified by:
getSpace in class Allocator
Returns:
the space associated with this bump pointer

show

public final void show()
Print out the status of the allocator (for debugging)

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