org.mmtk.utility.alloc

Class BumpPointer

java.lang.Object

org.mmtk.utility.alloc.Allocator

org.mmtk.utility.alloc.BumpPointer

Direct Known Subclasses:

CopyLocal, ImmortalLocal, MarkCompactLocal

public class BumpPointer
extends Allocator

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

Fields

Modifier and Type	Field and Description
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

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	BumpPointer(Space space, boolean allowScanning) Constructor.

Method Summary

Modifier and Type	Method and Description
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) Stores 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)

Stores the limit value at the end of the region.

Parameters:

region - region address

limit - the limit value

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)

bytes - the size of the pending allocation, if any

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)