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.policy
Class SegregatedFreeListSpace

java.lang.Object
  extended by org.mmtk.policy.Space
      extended by org.mmtk.policy.SegregatedFreeListSpace
All Implemented Interfaces:
Constants
Direct Known Subclasses:
ExplicitFreeListSpace, MarkSweepSpace
public abstract class SegregatedFreeListSpace
extends Space
implements Constants

Each instance of this class corresponds to one mark-sweep *space*. Each of the instance methods of this class may be called by any thread (i.e. synchronization must be explicit in any instance or class method). This contrasts with the MarkSweepLocal, where instances correspond to *plan* instances and therefore to kernel threads. Thus unlike this class, synchronization is not necessary in the instance methods of MarkSweepLocal.

Nested Class Summary
static class SegregatedFreeListSpace.Sweeper
          A callback used to perform sweeping of a free list space.
 
Nested classes/interfaces inherited from class org.mmtk.policy.Space
Space.SpaceVisitor
 
Field Summary
protected  AddressArray availableBlockHead
           
private  int[] blockHeaderSize
           
private  byte[] blockSizeClass
           
private  int[] cellSize
           
private static boolean COMPACT_SIZE_CLASSES
           
protected  AddressArray consumedBlockHead
           
protected  AddressArray flushedBlockHead
           
protected static boolean LAZY_SWEEP
           
private static int LIVE_BYTES_PER_REGION
           
private static Extent LIVE_WORD_STRIDE
           
private static Word LIVE_WORD_STRIDE_MASK
           
protected  Lock lock
           
private static int LOG_BIT_COVERAGE
           
private static int LOG_LIVE_COVERAGE
           
private static int LOG_LIVE_WORD_STRIDE
           
protected static int MAX_CELL_SIZE
           
protected static int MAX_CELLS
           
static int MAX_FREELIST_OBJECT_BYTES
           
private static Extent META_DATA_OFFSET
           
protected static int META_DATA_PAGES_PER_REGION_NO_BITMAP
           
protected static int META_DATA_PAGES_PER_REGION_WITH_BITMAP
           
private static int METADATA_OVERHEAD
           
protected static int MIN_CELLS
           
private static int NET_META_DATA_BYTES_PER_REGION
           
private static int NEW_SIZECLASS_OVERHEAD
           
private static int OBJECT_LIVE_SHIFT
           
private static Word WORD_SHIFT_MASK
           
static float WORST_CASE_FRAGMENTATION
           
 
Fields inherited from class org.mmtk.policy.Space
AVAILABLE_BYTES, AVAILABLE_END, AVAILABLE_PAGES, AVAILABLE_START, BYTES_IN_CHUNK, contiguous, descriptor, extent, headDiscontiguousRegion, HEAP_END, HEAP_START, immortal, LOG_ADDRESS_SPACE, LOG_BYTES_IN_CHUNK, MAX_CHUNKS, MAX_SPACES, movable, PAGES_IN_CHUNK, pr, start, zeroed
 
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
SegregatedFreeListSpace(String name, int additionalMetadata, VMRequest vmRequest)
          The caller specifies the region of virtual memory to be used for this space.
 
Method Summary
protected abstract  Address advanceToBlock(Address block, int sizeClass)
          Prepare a block for allocation, returning a free list into the block.
private static Address alignToLiveStride(Address address)
          Align an address so that it corresponds to a live word boundary.
protected  void clearAllBlockMarks()
          Clear all block marks for this space.
protected  void clearBlockMark(Address block, Extent blockSize)
          Clear block marks for a block
protected static void clearLiveBit(Address address)
          Clear the live bit for a given address
protected static void clearLiveBit(ObjectReference object)
          Clear the live bit for a given object
protected  void clearLiveBits(Address block, int sizeClass)
          Clear all live bits for a block
protected  void consumeBlocks()
          Eagerly consume all remaining blocks.
protected  boolean containsLiveCell(Address block, Extent blockSize, boolean clearMarks)
          Does this block contain any live cells.
private  Address expandSizeClass(int sizeClass, AddressArray freeList)
          Expand a particular size class, allocating a new block, breaking the block into cells and placing those cells on a free list for that block.
protected  void flushAvailableBlocks()
          Flush all the allocation blocks to the consumed list.
 Address getAllocationBlock(int sizeClass, AddressArray freeList)
          Acquire a new block from the global pool to allocate into.
 int getBaseCellSize(int sc)
          Return the size of a basic cell (i.e. not including any cell header) for a given size class.
protected  Address getFreeList(Address block)
          In the case where free lists associated with each block are preserved, get the free list for a given block.
private static Address getLiveWordAddress(Address address)
          Given an address, return the address of the live word for that address.
private static Word getMask(Address address, boolean set)
          Given an address, produce a bit mask for the live table
 int getSizeClass(int bytes)
          Get the size class for a given number of bytes.
private  Address getSweepBlock(int sizeClass)
          Get a block for a parallel sweep.
private  void initSizeClasses()
          Initialize the size class data structures.
protected  boolean isCellLive(ObjectReference object)
          In the cell containing this object live?
protected static boolean liveBitSet(Address address)
          Set the live bit for a given address
protected static boolean liveBitSet(ObjectReference object)
          Test the live bit for a given object
protected abstract  boolean maintainSideBitmap()
          Should SegregatedFreeListSpace manage a side bitmap to keep track of live objects?
protected  Address makeFreeList(Address block, int sizeClass)
          Use the live bits for a block to infer free cells and thus construct a free list for the block.
protected static void markBlock(Address block)
          Set the live bit for the given block.
protected static void markBlock(ObjectReference object)
          Set the live bit for the block containing the given object
protected  void notifyNewBlock(Address block, int sizeClass)
          Notify that a new block has been installed.
 void parallelSweepCells(SegregatedFreeListSpace.Sweeper sweeper)
          Sweep a block, freeing it and making it available if any live cells were found.
protected abstract  boolean preserveFreeList()
          Do we need to preserve free lists as we move blocks around.
protected  boolean reclaimCellForObject(ObjectReference object)
          Should the sweep reclaim the cell containing this object.
 void returnBlock(Address block, int sizeClass, Address freeCell)
          Return a block to the global pool.
 void returnConsumedBlock(Address block, int sizeClass)
          Return a block to the global pool.
protected  void setFreeList(Address block, Address cell)
          In the case where free lists associated with each block are preserved, set the free list for a given block.
static int sizeClassCount()
          The number of distinct size classes.
protected  Address sweepBlock(Address block, int sizeClass, Extent blockSize, Address availableHead, boolean clearMarks)
          Sweep a block, freeing it and adding to the list given by availableHead if it contains no free objects.
 void sweepCells(SegregatedFreeListSpace.Sweeper sweeper)
          Sweep all blocks for free objects.
 boolean sweepCells(SegregatedFreeListSpace.Sweeper sweeper, Address block, int sizeClass)
          Does this block contain any live cells?
private  Address sweepCells(SegregatedFreeListSpace.Sweeper sweeper, Address block, int sizeClass, Address availableHead)
          Sweep a block, freeing it and adding to the list given by availableHead if it contains no free objects.
protected  void sweepConsumedBlocks(boolean clearMarks)
          Sweep all blocks for free objects.
static boolean testAndSetLiveBit(ObjectReference object)
          Atomically set the live bit for a given object
protected static void unsyncClearLiveBit(Address address)
          Clear the live bit for a given address
protected static void unsyncClearLiveBit(ObjectReference object)
          Clear the live bit for a given object
static boolean unsyncSetLiveBit(ObjectReference object)
          Set the live bit for a given object, without using synchronization primitives---must only be used when contention for live bit is strictly not possible
private static boolean updateLiveBit(Address address, boolean set, boolean atomic)
          Set the live bit for a given address
protected  void zeroLiveBits()
           
 
Methods inherited from class org.mmtk.policy.Space
acquire, availablePhysicalPages, chunkAlign, chunkAlign, committedPages, cumulativeCommittedPages, eagerlyMmapMMTkContiguousSpaces, eagerlyMmapMMTkDiscontiguousSpaces, eagerlyMmapMMTkSpaces, getDescriptor, getDiscontigEnd, getDiscontigStart, getExtent, getFracAvailable, getHeadDiscontiguousRegion, getIndex, getName, getSpaceForAddress, getSpaceForObject, getStart, growDiscontiguousSpace, growSpace, isImmortal, isImmortal, isInSpace, isInSpace, isLive, isMappedAddress, isMappedObject, isMovable, isMovable, isReachable, printUsageMB, printUsagePages, printVMMap, release, releaseAllChunks, releaseDiscontiguousChunks, requiredChunks, reservedPages, setZeroingApproach, skipConcurrentZeroing, traceObject, triggerConcurrentZeroing, visitSpaces
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

LAZY_SWEEP

protected static final boolean LAZY_SWEEP
See Also:
Constant Field Values

COMPACT_SIZE_CLASSES

private static final boolean COMPACT_SIZE_CLASSES
See Also:
Constant Field Values

MIN_CELLS

protected static final int MIN_CELLS
See Also:
Constant Field Values

MAX_CELLS

protected static final int MAX_CELLS
See Also:
Constant Field Values

MAX_CELL_SIZE

protected static final int MAX_CELL_SIZE
See Also:
Constant Field Values

MAX_FREELIST_OBJECT_BYTES

public static final int MAX_FREELIST_OBJECT_BYTES
See Also:
Constant Field Values

OBJECT_LIVE_SHIFT

private static final int OBJECT_LIVE_SHIFT

LOG_BIT_COVERAGE

private static final int LOG_BIT_COVERAGE

LOG_LIVE_COVERAGE

private static final int LOG_LIVE_COVERAGE

LIVE_BYTES_PER_REGION

private static final int LIVE_BYTES_PER_REGION

WORD_SHIFT_MASK

private static final Word WORD_SHIFT_MASK

LOG_LIVE_WORD_STRIDE

private static final int LOG_LIVE_WORD_STRIDE

LIVE_WORD_STRIDE

private static final Extent LIVE_WORD_STRIDE

LIVE_WORD_STRIDE_MASK

private static final Word LIVE_WORD_STRIDE_MASK

NET_META_DATA_BYTES_PER_REGION

private static final int NET_META_DATA_BYTES_PER_REGION

META_DATA_PAGES_PER_REGION_WITH_BITMAP

protected static final int META_DATA_PAGES_PER_REGION_WITH_BITMAP

META_DATA_PAGES_PER_REGION_NO_BITMAP

protected static final int META_DATA_PAGES_PER_REGION_NO_BITMAP

META_DATA_OFFSET

private static final Extent META_DATA_OFFSET

NEW_SIZECLASS_OVERHEAD

private static final int NEW_SIZECLASS_OVERHEAD

METADATA_OVERHEAD

private static final int METADATA_OVERHEAD

WORST_CASE_FRAGMENTATION

public static final float WORST_CASE_FRAGMENTATION

lock

protected final Lock lock

consumedBlockHead

protected final AddressArray consumedBlockHead

flushedBlockHead

protected final AddressArray flushedBlockHead

availableBlockHead

protected final AddressArray availableBlockHead

cellSize

private final int[] cellSize

blockSizeClass

private final byte[] blockSizeClass

blockHeaderSize

private final int[] blockHeaderSize
Constructor Detail

SegregatedFreeListSpace

public SegregatedFreeListSpace(String name,
                               int additionalMetadata,
                               VMRequest vmRequest)
The caller specifies the region of virtual memory to be used for this space. If this region conflicts with an existing space, then the constructor will fail.

Parameters:
name - The name of this space (used when printing error messages etc)
additionalMetadata - The number of meta data bytes per region for the subclass.
vmRequest - An object describing the virtual memory requested.
Method Detail

maintainSideBitmap

protected abstract boolean maintainSideBitmap()
Should SegregatedFreeListSpace manage a side bitmap to keep track of live objects?

preserveFreeList

protected abstract boolean preserveFreeList()
Do we need to preserve free lists as we move blocks around.

returnConsumedBlock

public void returnConsumedBlock(Address block,
                                int sizeClass)
Return a block to the global pool.

Parameters:
block - The block to return
sizeClass - The size class

returnBlock

public void returnBlock(Address block,
                        int sizeClass,
                        Address freeCell)
Return a block to the global pool.

Parameters:
block - The block to return
sizeClass - The size class
freeCell - The first free cell in the block.

getAllocationBlock

public Address getAllocationBlock(int sizeClass,
                                  AddressArray freeList)
Acquire a new block from the global pool to allocate into. This method with either return a non-empty free list, or zero when allocation fails. This method will populate the passed in free list for the given size class and return the address of the block.

Parameters:
sizeClass - The size class to allocate into
freeList - The free list to populate
Returns:
The address of the block

expandSizeClass

private Address expandSizeClass(int sizeClass,
                                AddressArray freeList)
Expand a particular size class, allocating a new block, breaking the block into cells and placing those cells on a free list for that block. The block becomes the current head for this size class and the address of the first available cell is returned.

This is guaranteed to return pre-zeroed cells

Parameters:
sizeClass - The size class to be expanded
freeList - The free list to populate.
Returns:
The block that was just allocated.

initSizeClasses

private void initSizeClasses()
Initialize the size class data structures.

getSizeClass

public final int getSizeClass(int bytes)
Get the size class for a given number of bytes.

We use size classes based on a worst case internal fragmentation loss target of 1/8. In fact, across sizes from 8 bytes to 512 the average worst case loss is 13.3%, giving an expected loss (assuming uniform distribution) of about 7%. We avoid using the Lea class sizes because they were so numerous and therefore liable to lead to excessive inter-class-size fragmentation.

This method may segregate arrays and scalars (currently it does not).

This method should be more intelligent and take alignment requests into consideration. The issue with this is that the block header which can be varied by subclasses can change the alignment of the cells.

Parameters:
bytes - The number of bytes required to accommodate the object to be allocated.
Returns:
The size class capable of accommodating the allocation request.

getBaseCellSize

public final int getBaseCellSize(int sc)
Return the size of a basic cell (i.e. not including any cell header) for a given size class.

Parameters:
sc - The size class in question
Returns:
The size of a basic cell (i.e. not including any cell header).

sizeClassCount

public static int sizeClassCount()
The number of distinct size classes.

advanceToBlock

protected abstract Address advanceToBlock(Address block,
                                          int sizeClass)
Prepare a block for allocation, returning a free list into the block.

Parameters:
block - The new block
sizeClass - The block's sizeclass.

notifyNewBlock

protected void notifyNewBlock(Address block,
                              int sizeClass)
Notify that a new block has been installed. This is to ensure that appropriate collection state can be initialized for the block

Parameters:
block - The new block
sizeClass - The block's sizeclass.

reclaimCellForObject

protected boolean reclaimCellForObject(ObjectReference object)
Should the sweep reclaim the cell containing this object. Is this object live. This is only used when maintainSideBitmap is false.

Parameters:
object - The object to query
Returns:
true if the cell should be reclaimed

getFreeList

protected final Address getFreeList(Address block)
In the case where free lists associated with each block are preserved, get the free list for a given block.

Parameters:
block - The block whose free list is to be found
Returns:
The free list for this block

setFreeList

protected final void setFreeList(Address block,
                                 Address cell)
In the case where free lists associated with each block are preserved, set the free list for a given block.

Parameters:
block - The block whose free list is to be found
cell - The head of the free list (i.e. the first cell in the free list).

clearAllBlockMarks

protected final void clearAllBlockMarks()
Clear all block marks for this space. This method is important when it is desirable to do partial collections, which man mean that block marks need to be explicitly cleared when necessary.

sweepConsumedBlocks

protected final void sweepConsumedBlocks(boolean clearMarks)
Sweep all blocks for free objects.

Parameters:
clearMarks - should we clear block mark bits as we process.

sweepBlock

protected final Address sweepBlock(Address block,
                                   int sizeClass,
                                   Extent blockSize,
                                   Address availableHead,
                                   boolean clearMarks)
Sweep a block, freeing it and adding to the list given by availableHead if it contains no free objects.

Parameters:
clearMarks - should we clear block mark bits as we process.

consumeBlocks

protected final void consumeBlocks()
Eagerly consume all remaining blocks.

flushAvailableBlocks

protected final void flushAvailableBlocks()
Flush all the allocation blocks to the consumed list.

containsLiveCell

protected boolean containsLiveCell(Address block,
                                   Extent blockSize,
                                   boolean clearMarks)
Does this block contain any live cells.

Parameters:
block - The block
blockSize - The size of the block
clearMarks - should we clear block mark bits as we process.
Returns:
true if any cells in the block are live

clearBlockMark

protected void clearBlockMark(Address block,
                              Extent blockSize)
Clear block marks for a block

Parameters:
block - The block
blockSize - The size of the block

isCellLive

protected boolean isCellLive(ObjectReference object)
In the cell containing this object live?

Parameters:
object - The object
Returns:
true if the cell is live

makeFreeList

protected final Address makeFreeList(Address block,
                                     int sizeClass)
Use the live bits for a block to infer free cells and thus construct a free list for the block.

Parameters:
block - The block to be processed
sizeClass - The size class for the block
Returns:
The head of the new free list

sweepCells

public void sweepCells(SegregatedFreeListSpace.Sweeper sweeper)
Sweep all blocks for free objects.

sweepCells

private Address sweepCells(SegregatedFreeListSpace.Sweeper sweeper,
                           Address block,
                           int sizeClass,
                           Address availableHead)
Sweep a block, freeing it and adding to the list given by availableHead if it contains no free objects.

parallelSweepCells

public void parallelSweepCells(SegregatedFreeListSpace.Sweeper sweeper)
Sweep a block, freeing it and making it available if any live cells were found. if it contains no free objects.

This is designed to be called in parallel by multiple collector threads.

getSweepBlock

private Address getSweepBlock(int sizeClass)
Get a block for a parallel sweep.

Parameters:
sizeClass - The size class of the block to sweep.
Returns:
The block or zero if no blocks remain to be swept.

sweepCells

public boolean sweepCells(SegregatedFreeListSpace.Sweeper sweeper,
                          Address block,
                          int sizeClass)
Does this block contain any live cells?

testAndSetLiveBit

public static boolean testAndSetLiveBit(ObjectReference object)
Atomically set the live bit for a given object

Parameters:
object - The object whose live bit is to be set.
Returns:
true if the bit was changed to true.

markBlock

protected static void markBlock(ObjectReference object)
Set the live bit for the block containing the given object

Parameters:
object - The object whose blocks liveness is to be set.

markBlock

protected static void markBlock(Address block)
Set the live bit for the given block.

Parameters:
block - The block whose liveness is to be set.

unsyncSetLiveBit

public static boolean unsyncSetLiveBit(ObjectReference object)
Set the live bit for a given object, without using synchronization primitives---must only be used when contention for live bit is strictly not possible

Parameters:
object - The object whose live bit is to be set.

updateLiveBit

private static boolean updateLiveBit(Address address,
                                     boolean set,
                                     boolean atomic)
Set the live bit for a given address

Parameters:
address - The address whose live bit is to be set.
set - true if the bit is to be set, as opposed to cleared
atomic - true if we want to perform this operation atomically

liveBitSet

protected static boolean liveBitSet(ObjectReference object)
Test the live bit for a given object

Parameters:
object - The object whose live bit is to be set.

liveBitSet

protected static boolean liveBitSet(Address address)
Set the live bit for a given address

Parameters:
address - The address whose live bit is to be set.
Returns:
true if this operation changed the state of the live bit.

clearLiveBit

protected static void clearLiveBit(ObjectReference object)
Clear the live bit for a given object

Parameters:
object - The object whose live bit is to be cleared.

clearLiveBit

protected static void clearLiveBit(Address address)
Clear the live bit for a given address

Parameters:
address - The address whose live bit is to be cleared.

unsyncClearLiveBit

protected static void unsyncClearLiveBit(ObjectReference object)
Clear the live bit for a given object

Parameters:
object - The object whose live bit is to be cleared.

unsyncClearLiveBit

protected static void unsyncClearLiveBit(Address address)
Clear the live bit for a given address

Parameters:
address - The address whose live bit is to be cleared.

clearLiveBits

protected void clearLiveBits(Address block,
                             int sizeClass)
Clear all live bits for a block

zeroLiveBits

protected void zeroLiveBits()

alignToLiveStride

private static Address alignToLiveStride(Address address)
Align an address so that it corresponds to a live word boundary. In other words, if the live bit for the given address is not the zeroth bit of a live word, round the address down such that it does.

Parameters:
address - The address to be aligned to a live word
Returns:
The given address, aligned down so that it corresponds to an address on a live word boundary.

getMask

private static Word getMask(Address address,
                            boolean set)
Given an address, produce a bit mask for the live table

Parameters:
address - The address whose live bit mask is to be established
set - True if we want the mask for setting the bit, false if we want the mask for clearing the bit.
Returns:
The appropriate bit mask for object for the live table for.

getLiveWordAddress

private static Address getLiveWordAddress(Address address)
Given an address, return the address of the live word for that address.

Parameters:
address - The address whose live word address is to be returned
Returns:
The address of the live word for this object
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