| /* |
| * This file is part of the Jikes RVM project (http://jikesrvm.org). |
| * |
| * This file is licensed to You under the Eclipse Public License (EPL); |
| * You may not use this file except in compliance with the License. You |
| * may obtain a copy of the License at |
| * |
| * http://www.opensource.org/licenses/eclipse-1.0.php |
| * |
| * See the COPYRIGHT.txt file distributed with this work for information |
| * regarding copyright ownership. |
| */ |
| package org.mmtk.policy; |
| |
| import org.mmtk.plan.Plan; |
| import org.mmtk.plan.TransitiveClosure; |
| import org.mmtk.utility.heap.*; |
| import org.mmtk.utility.options.Options; |
| import org.mmtk.utility.options.MarkSweepMarkBits; |
| import org.mmtk.utility.options.EagerCompleteSweep; |
| import org.mmtk.utility.Constants; |
| |
| import org.mmtk.vm.VM; |
| |
| import org.vmmagic.pragma.*; |
| import org.vmmagic.unboxed.*; |
| |
| /** |
| * 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. |
| */ |
| @Uninterruptible |
| public final class MarkSweepSpace extends SegregatedFreeListSpace implements Constants { |
| |
| /**************************************************************************** |
| * |
| * Class variables |
| */ |
| /** |
| * Select between using mark bits in a side bitmap, or mark bits |
| * in the headers of object (or other sub-class scheme), and a single |
| * mark bit per block. |
| */ |
| public static final boolean HEADER_MARK_BITS = VM.config.HEADER_MARK_BITS; |
| /** highest bit bits we may use */ |
| private static final int MAX_BITS = 4; |
| |
| /* mark bits */ |
| private static final int COUNT_BASE = 0; |
| public static final int DEFAULT_MARKCOUNT_BITS = 2; |
| public static final int MAX_MARKCOUNT_BITS = Plan.NEEDS_LOG_BIT_IN_HEADER ? MAX_BITS - 1 : MAX_BITS; |
| public static final Word UNLOGGED_BIT = Word.one().lsh(MAX_BITS - 1).lsh(COUNT_BASE); |
| private static final Word MARK_COUNT_INCREMENT = Word.one().lsh(COUNT_BASE); |
| private static final Word MARK_COUNT_MASK = Word.one().lsh(MAX_MARKCOUNT_BITS).minus(Word.one()).lsh(COUNT_BASE); |
| private static final Word MARK_BITS_MASK = Word.one().lsh(MAX_BITS).minus(Word.one()); |
| |
| private static final boolean EAGER_MARK_CLEAR = Plan.NEEDS_LOG_BIT_IN_HEADER; |
| |
| /* header requirements */ |
| public static final int LOCAL_GC_BITS_REQUIRED = MAX_BITS; |
| public static final int GLOBAL_GC_BITS_REQUIRED = 0; |
| public static final int GC_HEADER_WORDS_REQUIRED = 0; |
| |
| |
| /**************************************************************************** |
| * |
| * Instance variables |
| */ |
| private Word markState = Word.one(); |
| private Word allocState = Word.zero(); |
| private boolean inMSCollection; |
| private static final boolean usingStickyMarkBits = VM.activePlan.constraints().needsLogBitInHeader(); /* are sticky mark bits in use? */ |
| private boolean isAgeSegregated = false; /* is this space a nursery space? */ |
| |
| /**************************************************************************** |
| * |
| * Initialization |
| */ |
| |
| static { |
| Options.markSweepMarkBits = new MarkSweepMarkBits(); |
| Options.eagerCompleteSweep = new EagerCompleteSweep(); |
| } |
| |
| /** |
| * 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. |
| * |
| * @param name The name of this space (used when printing error messages etc) |
| * @param pageBudget The number of pages this space may consume |
| * before consulting the plan |
| * @param vmRequest An object describing the virtual memory requested. |
| */ |
| public MarkSweepSpace(String name, int pageBudget, VMRequest vmRequest) { |
| super(name, pageBudget, 0, vmRequest); |
| if (usingStickyMarkBits) allocState = allocState.or(UNLOGGED_BIT); |
| } |
| |
| /** |
| * This instance will be age-segregated using the sticky mark bits |
| * algorithm. Perform appropriate initialization |
| */ |
| public void isAgeSegregatedSpace() { |
| /* we must be using sticky mark bits */ |
| if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(usingStickyMarkBits); |
| allocState = allocState.and(UNLOGGED_BIT.not()); /* clear the unlogged bit for nursery allocs */ |
| isAgeSegregated = true; |
| } |
| |
| /** |
| * Should SegregatedFreeListSpace manage a side bitmap to keep track of live objects? |
| */ |
| @Inline |
| protected boolean maintainSideBitmap() { |
| return !HEADER_MARK_BITS; |
| } |
| |
| /** |
| * Do we need to preserve free lists as we move blocks around. |
| */ |
| @Inline |
| protected boolean preserveFreeList() { |
| return !LAZY_SWEEP; |
| } |
| |
| /**************************************************************************** |
| * |
| * Allocation |
| */ |
| |
| /** |
| * Prepare the next block in the free block list for use by the free |
| * list allocator. In the case of lazy sweeping this involves |
| * sweeping the available cells. <b>The sweeping operation must |
| * ensure that cells are pre-zeroed</b>, as this method must return |
| * pre-zeroed cells. |
| * |
| * @param block The block to be prepared for use |
| * @param sizeClass The size class of the block |
| * @return The address of the first pre-zeroed cell in the free list |
| * for this block, or zero if there are no available cells. |
| */ |
| protected Address advanceToBlock(Address block, int sizeClass) { |
| if (HEADER_MARK_BITS) { |
| if (inMSCollection) markBlock(block); |
| } |
| |
| if (LAZY_SWEEP) { |
| return makeFreeList(block, sizeClass); |
| } else { |
| return getFreeList(block); |
| } |
| } |
| |
| /** |
| * Notify that a new block has been installed. This is to ensure that |
| * appropriate collection state can be initialized for the block |
| * |
| * @param block The new block |
| * @param sizeClass The block's sizeclass. |
| */ |
| protected void notifyNewBlock(Address block, int sizeClass) { |
| if (HEADER_MARK_BITS) { |
| if (inMSCollection) markBlock(block); |
| } |
| } |
| |
| /**************************************************************************** |
| * |
| * Collection |
| */ |
| |
| /** |
| * Prepare for a new collection increment. For the mark-sweep |
| * collector we must flip the state of the mark bit between |
| * collections. |
| * |
| * @param gcWholeMS True if we are going to collect the whole marksweep space |
| */ |
| public void prepare(boolean gcWholeMS) { |
| if (HEADER_MARK_BITS && Options.eagerCompleteSweep.getValue()) { |
| consumeBlocks(); |
| } else { |
| flushAvailableBlocks(); |
| } |
| if (HEADER_MARK_BITS) { |
| if (gcWholeMS) { |
| allocState = markState; |
| if (usingStickyMarkBits && !isAgeSegregated) /* if true, we allocate as "mature", not nursery */ |
| allocState = allocState.or(UNLOGGED_BIT); |
| markState = deltaMarkState(true); |
| if (EAGER_MARK_CLEAR) |
| clearAllBlockMarks(); |
| } |
| } else { |
| zeroLiveBits(start, ((FreeListPageResource) pr).getHighWater()); |
| } |
| inMSCollection = true; |
| } |
| |
| /** |
| * A new collection increment has completed. For the mark-sweep |
| * collector this means we can perform the sweep phase. |
| */ |
| public void release() { |
| sweepConsumedBlocks(!EAGER_MARK_CLEAR); |
| inMSCollection = false; |
| } |
| |
| /** |
| * Release an allocated page or pages |
| * |
| * @param start The address of the start of the page or pages |
| */ |
| @Inline |
| public void release(Address start) { |
| ((FreeListPageResource) pr).releasePages(start); |
| } |
| |
| /** |
| * Should the sweep reclaim the cell containing this object. Is this object |
| * live. This is only used when maintainSideBitmap is false. |
| * |
| * @param object The object to query |
| * @return True if the cell should be reclaimed |
| */ |
| @Inline |
| protected boolean isCellLive(ObjectReference object) { |
| if (!HEADER_MARK_BITS) { |
| return super.isCellLive(object); |
| } |
| return testMarkState(object, markState); |
| } |
| |
| /**************************************************************************** |
| * |
| * Object processing and tracing |
| */ |
| |
| /** |
| * Trace a reference to an object under a mark sweep collection |
| * policy. If the object header is not already marked, mark the |
| * object in either the bitmap or by moving it off the treadmill, |
| * and enqueue the object for subsequent processing. The object is |
| * marked as (an atomic) side-effect of checking whether already |
| * marked. |
| * |
| * @param object The object to be traced. |
| * @return The object (there is no object forwarding in this |
| * collector, so we always return the same object: this could be a |
| * void method but for compliance to a more general interface). |
| */ |
| @Inline |
| public ObjectReference traceObject(TransitiveClosure trace, ObjectReference object) { |
| if (HEADER_MARK_BITS) { |
| Word markValue = Plan.NEEDS_LOG_BIT_IN_HEADER ? markState.or(Plan.UNLOGGED_BIT) : markState; |
| if (testAndMark(object, markValue)) { |
| markBlock(object); |
| trace.processNode(object); |
| } |
| } else { |
| if (testAndSetLiveBit(object)) { |
| trace.processNode(object); |
| } |
| } |
| return object; |
| } |
| |
| /** |
| * |
| * @param object The object in question |
| * @return True if this object is known to be live (i.e. it is marked) |
| */ |
| @Inline |
| public boolean isLive(ObjectReference object) { |
| if (HEADER_MARK_BITS) { |
| return testMarkState(object, markState); |
| } else { |
| return liveBitSet(object); |
| } |
| } |
| |
| /** |
| * Get the current mark state |
| * |
| * @return The current mark state. |
| */ |
| @Inline |
| public Word getMarkState() { |
| if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(markState.and(MARK_COUNT_MASK.not()).isZero()); |
| return markState; |
| } |
| |
| /** |
| * Get the previous mark state. |
| * |
| * @return The previous mark state. |
| */ |
| @Inline |
| public Word getPreviousMarkState() { |
| return deltaMarkState(false); |
| } |
| |
| /** |
| * Return the mark state incremented or decremented by one. |
| * |
| * @param increment If true, then return the incremented value else return the decremented value |
| * @return the mark state incremented or decremented by one. |
| */ |
| private Word deltaMarkState(boolean increment) { |
| Word mask = Word.fromIntZeroExtend((1 << Options.markSweepMarkBits.getValue()) - 1).lsh(COUNT_BASE); |
| Word rtn = increment ? markState.plus(MARK_COUNT_INCREMENT) : markState.minus(MARK_COUNT_INCREMENT); |
| rtn = rtn.and(mask); |
| if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(markState.and(MARK_COUNT_MASK.not()).isZero()); |
| return rtn; |
| } |
| |
| /**************************************************************************** |
| * |
| * Header manipulation |
| */ |
| |
| /** |
| * Perform any required post allocation initialization |
| * |
| * @param object the object ref to the storage to be initialized |
| */ |
| @Inline |
| public void postAlloc(ObjectReference object) { |
| initializeHeader(object, true); |
| } |
| |
| /** |
| * Perform any required post copy (i.e. in-GC allocation) initialization. |
| * This is relevant (for example) when MS is used as the mature space in |
| * a copying GC. |
| * |
| * @param object the object ref to the storage to be initialized |
| * @param majorGC Is this copy happening during a major gc? |
| */ |
| @Inline |
| public void postCopy(ObjectReference object, boolean majorGC) { |
| initializeHeader(object, false); |
| if (!HEADER_MARK_BITS) { |
| testAndSetLiveBit(object); |
| } |
| } |
| |
| /** |
| * Perform any required initialization of the GC portion of the header. |
| * |
| * @param object the object ref to the storage to be initialized |
| * @param alloc is this initialization occuring due to (initial) allocation |
| * (true) or due to copying (false)? |
| */ |
| @Inline |
| public void initializeHeader(ObjectReference object, boolean alloc) { |
| if (HEADER_MARK_BITS) { |
| if (alloc) { |
| writeAllocState(object); |
| } else { |
| writeMarkState(object); |
| } |
| } |
| } |
| |
| /** |
| * Atomically attempt to set the mark bit of an object. Return true |
| * if successful, false if the mark bit was already set. |
| * |
| * @param object The object whose mark bit is to be written |
| * @param value The value to which the mark bits will be set |
| */ |
| @Inline |
| private static boolean testAndMark(ObjectReference object, Word value) { |
| int oldValue, markBits; |
| oldValue = VM.objectModel.readAvailableByte(object); |
| markBits = oldValue & MARK_BITS_MASK.toInt(); |
| if (markBits == value.toInt()) return false; |
| VM.objectModel.writeAvailableByte(object, (byte)(oldValue & ~MARK_BITS_MASK.toInt() | value.toInt())); |
| return true; |
| } |
| |
| /** |
| * Return true if the mark count for an object has the given value. |
| * |
| * @param object The object whose mark bit is to be tested |
| * @param value The value against which the mark bit will be tested |
| * @return True if the mark bit for the object has the given value. |
| */ |
| @Inline |
| public static boolean testMarkState(ObjectReference object, Word value) { |
| if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(value.and(MARK_COUNT_MASK.not()).isZero()); |
| return VM.objectModel.readAvailableBitsWord(object).and(MARK_COUNT_MASK).EQ(value); |
| } |
| |
| /** |
| * Write the allocState into the mark state fields of an object non-atomically. |
| * This is appropriate for allocation time initialization. |
| * |
| * @param object The object whose mark state is to be written |
| */ |
| @Inline |
| private void writeAllocState(ObjectReference object) { |
| Word oldValue = VM.objectModel.readAvailableBitsWord(object); |
| Word newValue = oldValue.and(MARK_BITS_MASK.not()).or(allocState); |
| VM.objectModel.writeAvailableBitsWord(object, newValue); |
| } |
| |
| /** |
| * Write the markState into the mark state fields of an object non-atomically. |
| * This is appropriate for collection time initialization. |
| * |
| * @param object The object whose mark state is to be written |
| */ |
| @Inline |
| private void writeMarkState(ObjectReference object) { |
| Word oldValue = VM.objectModel.readAvailableBitsWord(object); |
| Word newValue = oldValue.and(MARK_BITS_MASK.not()).or(markState); |
| VM.objectModel.writeAvailableBitsWord(object, newValue); |
| } |
| } |