| /* |
| * 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.TraceLocal; |
| import org.mmtk.plan.TransitiveClosure; |
| import org.mmtk.utility.heap.*; |
| import org.mmtk.utility.options.Options; |
| import org.mmtk.utility.Constants; |
| import org.mmtk.utility.Log; |
| |
| import org.mmtk.vm.VM; |
| |
| import org.vmmagic.unboxed.*; |
| import org.vmmagic.pragma.*; |
| |
| /** |
| * This class implements tracing functionality for a simple copying |
| * space. Since no state needs to be held globally or locally, all |
| * methods are static. |
| */ |
| @Uninterruptible public final class CopySpace extends Space |
| implements Constants { |
| |
| /**************************************************************************** |
| * |
| * Class variables |
| */ |
| public static final int LOCAL_GC_BITS_REQUIRED = 2; |
| public static final int GLOBAL_GC_BITS_REQUIRED = 0; |
| public static final int GC_HEADER_WORDS_REQUIRED = 0; |
| |
| private static final int META_DATA_PAGES_PER_REGION = CARD_META_PAGES_PER_REGION; |
| |
| /* |
| * The forwarding process uses three states to deal with a GC race: |
| * 1. !GC_FORWARDED: Unforwarded |
| * 2. GC_BEING_FORWARDED: Being forwarded (forwarding is underway) |
| * 3. GC_FORWARDED: Forwarded |
| */ |
| /** If this bit is set, then forwarding of this object has commenced */ |
| private static final Word GC_FORWARDED = Word.one().lsh(1); // ...10 |
| /** If this bit is set, then forwarding of this object is incomplete */ |
| private static final Word GC_BEING_FORWARDED = Word.one().lsh(2).minus(Word.one()); // ...11 |
| /** This mask is used to reveal which state this object is in with respect to forwarding */ |
| private static final Word GC_FORWARDING_MASK = GC_FORWARDED.or(GC_BEING_FORWARDED); |
| |
| /** A single bit is used to indicate a mark when tracing (but not copying) the space */ |
| private static final Word GC_MARK_BIT_MASK = Word.one(); |
| |
| /**************************************************************************** |
| * |
| * Instance variables |
| */ |
| private boolean fromSpace = true; |
| |
| public boolean isFromSpace() { |
| return fromSpace; |
| } |
| |
| /**************************************************************************** |
| * |
| * Initialization |
| */ |
| |
| /** |
| * 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 fromSpace The does this instance start life as from-space |
| * (or to-space)? |
| * @param vmRequest An object describing the virtual memory requested. |
| */ |
| public CopySpace(String name, int pageBudget, boolean fromSpace, VMRequest vmRequest) { |
| super(name, true, false, vmRequest); |
| this.fromSpace = fromSpace; |
| if (vmRequest.isDiscontiguous()) { |
| pr = new MonotonePageResource(pageBudget, this, META_DATA_PAGES_PER_REGION); |
| } else { |
| pr = new MonotonePageResource(pageBudget, this, start, extent, META_DATA_PAGES_PER_REGION); |
| } |
| } |
| |
| /**************************************************************************** |
| * |
| * Prepare and release |
| */ |
| |
| /** |
| * Prepare this space instance for a collection. Set the |
| * "fromSpace" field according to whether this space is the |
| * source or target of the collection. |
| * |
| * @param fromSpace Set the fromSpace field to this value |
| */ |
| public void prepare(boolean fromSpace) { this.fromSpace = fromSpace; } |
| |
| /** |
| * Release this copy space after a collection. This means releasing |
| * all pages associated with this (now empty) space. |
| */ |
| public void release() { |
| ((MonotonePageResource) pr).reset(); |
| lastDiscontiguousRegion = Address.zero(); |
| fromSpace = false; |
| } |
| |
| /** |
| * Release an allocated page or pages. In this case we do nothing |
| * because we only release pages enmasse. |
| * |
| * @param start The address of the start of the page or pages |
| */ |
| @Inline |
| public void release(Address start) { |
| if (VM.VERIFY_ASSERTIONS) |
| VM.assertions._assert(false); // this policy only releases pages enmasse |
| } |
| |
| /**************************************************************************** |
| * |
| * Tracing and forwarding |
| */ |
| |
| /** |
| * Trace an object under a copying collection policy. |
| * |
| * We use a tri-state algorithm to deal with races to forward |
| * the object. The tracer must wait if the object is concurrently |
| * being forwarded by another thread. |
| * |
| * If the object is already forwarded, the copy is returned. |
| * Otherwise, the object is forwarded and the copy is returned. |
| * |
| * @param trace The trace being conducted. |
| * @param object The object to be forwarded. |
| * @return The forwarded object. |
| */ |
| @Inline |
| public ObjectReference traceObject(TransitiveClosure trace, ObjectReference object) { |
| VM.assertions.fail("CopySpace.traceLocal called without allocator"); |
| return ObjectReference.nullReference(); |
| } |
| |
| /** |
| * Trace an object under a copying collection policy. |
| * |
| * We use a tri-state algorithm to deal with races to forward |
| * the object. The tracer must wait if the object is concurrently |
| * being forwarded by another thread. |
| * |
| * If the object is already forwarded, the copy is returned. |
| * Otherwise, the object is forwarded and the copy is returned. |
| * |
| * @param trace The trace being conducted. |
| * @param object The object to be forwarded. |
| * @param allocator The allocator to use when copying. |
| * @return The forwarded object. |
| */ |
| @Inline |
| public ObjectReference traceObject(TransitiveClosure trace, ObjectReference object, int allocator) { |
| /* If the object in question is already in to-space, then do nothing */ |
| if (!fromSpace) return object; |
| |
| /* Try to forward the object */ |
| Word forwardingPtr = attemptToForward(object); |
| |
| if (stateIsForwardedOrBeingForwarded(forwardingPtr)) { |
| /* Somebody else got to it first. */ |
| |
| /* We must wait (spin) if the object is not yet fully forwarded */ |
| while (stateIsBeingForwarded(forwardingPtr)) |
| forwardingPtr = getForwardingWord(object); |
| |
| /* Now extract the object reference from the forwarding word and return it */ |
| return forwardingPtr.and(GC_FORWARDING_MASK.not()).toAddress().toObjectReference(); |
| } else { |
| /* We are the designated copier, so forward it and enqueue it */ |
| ObjectReference newObject = VM.objectModel.copy(object, allocator); |
| setForwardingPointer(object, newObject); |
| trace.processNode(newObject); // Scan it later |
| |
| if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() >= 9) { |
| Log.write("C["); Log.write(object); Log.write("/"); |
| Log.write(getName()); Log.write("] -> "); |
| Log.write(newObject); Log.write("/"); |
| Log.write(Space.getSpaceForObject(newObject).getName()); |
| Log.writeln("]"); |
| } |
| return newObject; |
| } |
| } |
| |
| /** |
| * Return true if this object is live in this GC |
| * |
| * @param object The object in question |
| * @return True if this object is live in this GC (has it been forwarded?) |
| */ |
| public boolean isLive(ObjectReference object) { |
| return isForwarded(object); |
| } |
| |
| /** |
| * Has the object in this space been reached during the current collection. |
| * This is used for GC Tracing. |
| * |
| * @param object The object reference. |
| * @return True if the object is reachable. |
| */ |
| public boolean isReachable(ObjectReference object) { |
| return !fromSpace || isForwarded(object); |
| } |
| |
| /**************************************************************************** |
| * |
| * Non-copying tracing (just mark, don't forward) |
| */ |
| |
| /** |
| * Mark an object as having been traversed, *WITHOUT* forwarding the object. |
| * This is only used when |
| * |
| * @param object The object to be marked |
| * @param markState The sense of the mark bit (flips from 0 to 1) |
| */ |
| @Inline |
| public static void markObject(TraceLocal trace, ObjectReference object, |
| Word markState) { |
| if (testAndMark(object, markState)) |
| trace.processNode(object); |
| } |
| |
| /**************************************************************************** |
| * |
| * Header manipulation |
| */ |
| |
| /** |
| * Perform any required post-allocation initialization |
| * |
| * <i>Nothing to be done in this case</i> |
| * |
| * @param object the object ref to the storage to be initialized |
| */ |
| @Inline |
| public void postAlloc(ObjectReference object) {} |
| |
| /** |
| * Clear the GC portion of the header for an object. |
| * |
| * @param object the object ref to the storage to be initialized |
| */ |
| @Inline |
| public static void clearGCBits(ObjectReference object) { |
| Word header = VM.objectModel.readAvailableBitsWord(object); |
| VM.objectModel.writeAvailableBitsWord(object, header.and(GC_FORWARDING_MASK.not())); |
| } |
| |
| /** |
| * Has an object been forwarded? |
| * |
| * @param object The object to be checked |
| * @return True if the object has been forwarded |
| */ |
| @Inline |
| public static boolean isForwarded(ObjectReference object) { |
| return stateIsForwarded(getForwardingWord(object)); |
| } |
| |
| /** |
| * Has an object been forwarded or being forwarded? |
| * |
| * @param object The object to be checked |
| * @return True if the object has been forwarded or is being forwarded |
| */ |
| @Inline |
| public static boolean isForwardedOrBeingForwarded(ObjectReference object) { |
| return stateIsForwardedOrBeingForwarded(getForwardingWord(object)); |
| } |
| |
| /** |
| * Non-atomic read of forwarding pointer word |
| * |
| * @param object The object whose forwarding word is to be read |
| * @return The forwarding word stored in <code>object</code>'s |
| * header. |
| */ |
| @Inline |
| private static Word getForwardingWord(ObjectReference object) { |
| return VM.objectModel.readAvailableBitsWord(object); |
| } |
| |
| /** |
| * Non-atomic read of forwarding pointer |
| * |
| * @param object The object whose forwarding pointer is to be read |
| * @return The forwarding pointer stored in <code>object</code>'s |
| * header. |
| */ |
| @Inline |
| public static ObjectReference getForwardingPointer(ObjectReference object) { |
| return getForwardingWord(object).and(GC_FORWARDING_MASK.not()).toAddress().toObjectReference(); |
| } |
| |
| /** |
| * Used to mark boot image objects during a parallel scan of objects |
| * during GC Returns true if marking was done. |
| * |
| * @param object The object to be marked |
| * @param value The value to store in the mark bit |
| */ |
| @Inline |
| private static boolean testAndMark(ObjectReference object, Word value) { |
| Word oldValue; |
| do { |
| oldValue = VM.objectModel.prepareAvailableBits(object); |
| Word markBit = oldValue.and(GC_MARK_BIT_MASK); |
| if (markBit.EQ(value)) return false; |
| } while (!VM.objectModel.attemptAvailableBits(object, oldValue, |
| oldValue.xor(GC_MARK_BIT_MASK))); |
| return true; |
| } |
| |
| /** |
| * Either return the forwarding pointer if the object is already |
| * forwarded (or being forwarded) or write the bit pattern that |
| * indicates that the object is being forwarded |
| * |
| * @param object The object to be forwarded |
| * @return The forwarding pointer for the object if it has already |
| * been forwarded. |
| */ |
| @Inline |
| private static Word attemptToForward(ObjectReference object) { |
| Word oldValue; |
| do { |
| oldValue = VM.objectModel.prepareAvailableBits(object); |
| if (oldValue.and(GC_FORWARDING_MASK).EQ(GC_FORWARDED)) return oldValue; |
| } while (!VM.objectModel.attemptAvailableBits(object, oldValue, |
| oldValue.or(GC_BEING_FORWARDED))); |
| return oldValue; |
| } |
| |
| /** |
| * Is the state of the forwarding word being forwarded? |
| * |
| * @param fword A forwarding word. |
| * @return True if the forwarding word's state is being forwarded. |
| */ |
| @Inline |
| private static boolean stateIsBeingForwarded(Word fword) { |
| return fword.and(GC_FORWARDING_MASK).EQ(GC_BEING_FORWARDED); |
| } |
| |
| /** |
| * Is the state of the forwarding word forwarded? |
| * |
| * @param fword A forwarding word. |
| * @return True if the forwarding word's state is forwarded. |
| */ |
| @Inline |
| private static boolean stateIsForwarded(Word fword) { |
| return fword.and(GC_FORWARDING_MASK).EQ(GC_FORWARDED); |
| } |
| |
| /** |
| * Is the state of the forwarding word forwarded or being forwarded? |
| * |
| * @param fword A forwarding word. |
| * @return True if the forwarding word's state is forwarded or being |
| * forwarded. |
| */ |
| @Inline |
| public static boolean stateIsForwardedOrBeingForwarded(Word fword) { |
| return !(fword.and(GC_FORWARDED).isZero()); |
| } |
| |
| /** |
| * Non-atomic write of forwarding pointer word (assumption, thread |
| * doing the set has done attempt to forward and owns the right to |
| * copy the object) |
| * |
| * @param object The object whose forwarding pointer is to be set |
| * @param ptr The forwarding pointer to be stored in the object's |
| * forwarding word |
| */ |
| @Inline |
| private static void setForwardingPointer(ObjectReference object, |
| ObjectReference ptr) { |
| VM.objectModel.writeAvailableBitsWord(object, ptr.toAddress().toWord().or(GC_FORWARDED)); |
| } |
| } |