001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.mmtk.policy;
014
015import org.mmtk.plan.TraceLocal;
016import org.mmtk.plan.TransitiveClosure;
017import org.mmtk.utility.alloc.BumpPointer;
018import org.mmtk.utility.heap.*;
019import org.mmtk.utility.Log;
020
021import org.mmtk.vm.Lock;
022import org.mmtk.vm.VM;
023
024import org.vmmagic.unboxed.*;
025import org.vmmagic.pragma.*;
026
027/**
028 * This class implements functionality for a simple sliding mark-compact
029 * space.
030 */
031@Uninterruptible public final class MarkCompactSpace extends Space {
032
033  /****************************************************************************
034   *
035   * Class variables
036   */
037
038  /**
039   *
040   */
041  public static final int LOCAL_GC_BITS_REQUIRED = 1;
042  public static final int GLOBAL_GC_BITS_REQUIRED = 0;
043  public static final int GC_HEADER_WORDS_REQUIRED = 1;
044
045  private static final Word GC_MARK_BIT_MASK = Word.one();
046  private static final Offset FORWARDING_POINTER_OFFSET = VM.objectModel.GC_HEADER_OFFSET();
047
048  private static final Lock lock = VM.newLock("mcSpace");
049
050  /** The list of occupied regions */
051  private Address regionList = Address.zero();
052
053  // TODO - maintain a separate list of partially allocated regions
054  // for threads to allocate into immediately after a collection.
055
056  /****************************************************************************
057   *
058   * Instance variables
059   */
060
061  /****************************************************************************
062   *
063   * Initialization
064   */
065
066  /**
067   * The caller specifies the region of virtual memory to be used for
068   * this space.  If this region conflicts with an existing space,
069   * then the constructor will fail.
070   *
071   * @param name The name of this space (used when printing error messages etc)
072   * @param vmRequest An object describing the virtual memory requested.
073   */
074  public MarkCompactSpace(String name, VMRequest vmRequest) {
075    super(name, true, false, true, vmRequest);
076    if (vmRequest.isDiscontiguous()) {
077      pr = new FreeListPageResource(this, 0);
078    } else {
079      pr = new FreeListPageResource(this, start, extent, 0);
080    }
081  }
082
083  /**
084   * Prepare for a collection
085   */
086  public void prepare() {
087  }
088
089  /**
090   * Release after a collection
091   */
092  public void release() {
093    // nothing to do
094  }
095
096
097  /**
098   * {@inheritDoc}<p>
099   *
100   * In this case we do nothing ecause we only release pages enmasse.
101   */
102  @Override
103  @Inline
104  public void release(Address start) {
105    ((FreeListPageResource)pr).releasePages(start);
106  }
107
108  /**
109   * Trace an object under a copying collection policy.
110   * If the object is already copied, the copy is returned.
111   * Otherwise, a copy is created and returned.
112   * In either case, the object will be marked on return.
113   *
114   * @param trace The trace being conducted.
115   * @param object The object to be forwarded.
116   * @return The forwarded object.
117   */
118  @Override
119  @Inline
120  public ObjectReference traceObject(TransitiveClosure trace, ObjectReference object) {
121    if (VM.VERIFY_ASSERTIONS)
122      VM.assertions._assert(false);
123    return null;
124  }
125
126  /**
127   * Trace an object under a copying collection policy.
128   * If the object is already copied, the copy is returned.
129   * Otherwise, a copy is created and returned.
130   * In either case, the object will be marked on return.
131   *
132   * @param trace The trace being conducted.
133   * @param object The object to be forwarded.
134   * @return The forwarded object.
135   */
136  @Inline
137  public ObjectReference traceMarkObject(TraceLocal trace, ObjectReference object) {
138    if (MarkCompactCollector.VERY_VERBOSE) {
139      Log.write("marking "); Log.write(object);
140    }
141    if (testAndMark(object)) {
142      trace.processNode(object);
143    } else if (!getForwardingPointer(object).isNull()) {
144      if (MarkCompactCollector.VERY_VERBOSE) {
145        Log.write(" -> "); Log.writeln(getForwardingPointer(object));
146      }
147      return getForwardingPointer(object);
148    }
149    if (MarkCompactCollector.VERY_VERBOSE) {
150      Log.writeln();
151    }
152    return object;
153  }
154
155  /**
156   * Trace an object under a copying collection policy.
157   * If the object is already copied, the copy is returned.
158   * Otherwise, a copy is created and returned.
159   * In either case, the object will be marked on return.
160   *
161   * @param trace The trace being conducted.
162   * @param object The object to be forwarded.
163   * @return The forwarded object.
164   */
165  @Inline
166  public ObjectReference traceForwardObject(TraceLocal trace, ObjectReference object) {
167    if (testAndClearMark(object)) {
168      trace.processNode(object);
169    }
170    ObjectReference newObject = getForwardingPointer(object);
171    if (MarkCompactCollector.VERY_VERBOSE) {
172      Log.write("forwarding "); Log.write(object);
173      Log.write(" -> "); Log.writeln(newObject);
174    }
175    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!newObject.isNull());
176    return getForwardingPointer(object);
177  }
178
179  @Override
180  public boolean isLive(ObjectReference object) {
181    return isMarked(object);
182  }
183
184  @Override
185  public boolean isReachable(ObjectReference object) {
186    return isMarked(object);
187  }
188
189
190  /****************************************************************************
191   *
192   * Header manipulation
193   */
194
195  /**
196   * Perform any required post-allocation initialization
197   *
198   * <i>Nothing to be done in this case</i>
199   *
200   * @param object the object ref to the storage to be initialized
201   */
202  @Inline
203  public void postAlloc(ObjectReference object) {
204  }
205
206  /**
207   * Non-atomic read of forwarding pointer
208   *
209   * @param object The object whose forwarding pointer is to be read
210   * @return The forwarding pointer stored in <code>object</code>'s
211   * header.
212   */
213  @Inline
214  public static ObjectReference getForwardingPointer(ObjectReference object) {
215    return object.toAddress().loadObjectReference(FORWARDING_POINTER_OFFSET);
216  }
217
218  /**
219   * Initialise the header of the object.
220   *
221   * @param object The object to initialise
222   */
223  @Inline
224  public void initializeHeader(ObjectReference object) {
225    // nothing to do
226  }
227
228  /**
229   * Used to mark boot image objects during a parallel scan of objects
230   * during GC.
231   *
232   * @param object The object to be marked
233   * @return {@code true} if marking was done.
234   */
235  @Inline
236  public static boolean testAndMark(ObjectReference object) {
237    Word oldValue;
238    do {
239      oldValue = VM.objectModel.prepareAvailableBits(object);
240      Word markBit = oldValue.and(GC_MARK_BIT_MASK);
241      if (!markBit.isZero()) return false;
242    } while (!VM.objectModel.attemptAvailableBits(object, oldValue,
243                                                oldValue.or(GC_MARK_BIT_MASK)));
244    return true;
245  }
246
247  /**
248   * @param object the object in question
249   * @return {@code true} if the object is marked
250   */
251  @Inline
252  public static boolean isMarked(ObjectReference object) {
253    Word oldValue = VM.objectModel.readAvailableBitsWord(object);
254    Word markBit = oldValue.and(GC_MARK_BIT_MASK);
255    return (!markBit.isZero());
256  }
257
258  /**
259   * Used to mark boot image objects during a parallel scan of objects
260   * during GC Returns true if marking was done.
261   *
262   * @param object The object to be marked
263   * @return {@code true} if marking was done, {@code false} otherwise
264   */
265  @Inline
266  private static boolean testAndClearMark(ObjectReference object) {
267    Word oldValue;
268    do {
269      oldValue = VM.objectModel.prepareAvailableBits(object);
270      Word markBit = oldValue.and(GC_MARK_BIT_MASK);
271      if (markBit.isZero()) return false;
272    } while (!VM.objectModel.attemptAvailableBits(object, oldValue,
273                                                oldValue.and(GC_MARK_BIT_MASK.not())));
274    return true;
275  }
276
277
278  @Inline
279  public static boolean toBeCompacted(ObjectReference object) {
280    Word oldValue = VM.objectModel.readAvailableBitsWord(object);
281    Word markBit = oldValue.and(GC_MARK_BIT_MASK);
282    return !markBit.isZero() && getForwardingPointer(object).isNull();
283  }
284
285  @Inline
286  public static void clearMark(ObjectReference object) {
287    Word oldValue = VM.objectModel.readAvailableBitsWord(object);
288    VM.objectModel.writeAvailableBitsWord(object, oldValue.and(GC_MARK_BIT_MASK.not()));
289  }
290
291  /**
292   * Non-atomic write of forwarding pointer word (assumption, thread
293   * doing the set has done attempt to forward and owns the right to
294   * copy the object)
295   *
296   * @param object The object whose forwarding pointer is to be set
297   * @param ptr The forwarding pointer to be stored in the object's
298   * forwarding word
299   */
300  @Inline
301  public static void setForwardingPointer(ObjectReference object,
302                                           ObjectReference ptr) {
303    object.toAddress().store(ptr.toAddress(), FORWARDING_POINTER_OFFSET);
304  }
305
306  /**
307   * Non-atomic clear of forwarding pointer word (assumption, thread
308   * doing the set has done attempt to forward and owns the right to
309   * copy the object)
310   *
311   * @param object The object whose forwarding pointer is to be set
312   */
313  @Inline
314  public static void clearForwardingPointer(ObjectReference object) {
315    object.toAddress().store(Address.zero(), FORWARDING_POINTER_OFFSET);
316  }
317
318  /**
319   * @return A region of this space that has net yet been compacted during
320   *   the current collection
321   */
322  public Address getNextRegion() {
323    lock.acquire();
324    if (regionList.isZero()) {
325      lock.release();
326      return Address.zero();
327    }
328    Address result = regionList;
329    regionList = BumpPointer.getNextRegion(regionList);
330    BumpPointer.clearNextRegion(result);
331    lock.release();
332    return result;
333  }
334
335  /**
336   * Append a region or list of regions to the global list
337   * @param region the region to append
338   */
339  public void append(Address region) {
340    lock.acquire();
341    if (MarkCompactCollector.VERBOSE) {
342      Log.write("Appending region "); Log.write(region);
343      Log.writeln(" to global list");
344    }
345    if (regionList.isZero()) {
346      regionList = region;
347    } else {
348      appendRegion(regionList,region);
349    }
350    lock.release();
351  }
352
353  public static void appendRegion(Address listHead, Address region) {
354    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!listHead.isZero());
355    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!region.isZero());
356    Address cursor = listHead;
357    while (!BumpPointer.getNextRegion(cursor).isZero()) {
358      cursor = BumpPointer.getNextRegion(cursor);
359    }
360    BumpPointer.setNextRegion(cursor,region);
361  }
362}