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.markcompact.MC;
016import org.mmtk.utility.Log;
017import org.mmtk.utility.alloc.Allocator;
018import org.mmtk.utility.alloc.BumpPointer;
019import org.mmtk.vm.VM;
020import org.vmmagic.pragma.Inline;
021import org.vmmagic.pragma.Uninterruptible;
022import org.vmmagic.unboxed.Address;
023import org.vmmagic.unboxed.Extent;
024import org.vmmagic.unboxed.ObjectReference;
025
026/**
027 * This class implements unsynchronized (local) per-collector-thread elements of a
028 * sliding mark-compact collector.
029 *<p>
030 * Specifically, this class provides the methods that
031 * <ul>
032 *  <li>Calculate the forwarding pointers for heap objects, in a linear pass over
033 *   (part of) the heap</li>
034 *  <li>Performs the compaction pass over the heap.</li>
035 * </ul>
036 *<p>
037 * Each collector thread maintains a private list of the pages that it compacts.
038 * If it runs out of work during the calculateForwardingPointers pass, it requests
039 * a new region from the global MarkCompactSpace.  Regions compacted by a collector
040 * remain local to the collector.
041 *
042 * @see MarkCompactSpace
043 * @see MarkCompactLocal
044 */
045@Uninterruptible
046public final class MarkCompactCollector {
047
048  static final boolean VERBOSE = false;
049
050  static final boolean VERY_VERBOSE = VERBOSE && false;
051
052  private final MarkCompactSpace space;
053
054  /**
055   * This collector's work list
056   */
057  private Address regions = Address.zero();
058
059  private final FromCursor fromCursor = new FromCursor();
060  private final ToCursor toCursor = new ToCursor();
061
062  /**
063   * Constructor
064   *
065   * @param space The space to bump point into.
066   */
067  public MarkCompactCollector(MarkCompactSpace space) {
068    this.space = space;
069  }
070
071  /* ********************************************************************************
072   *
073   *                Cursor classes
074   *
075   */
076
077  /**
078   * Both the 'compact' and 'calculate' phases can be thought of as sweeping
079   * a pair of cursors across a linked list of regions.  Each cursor requires
080   * maintaining pointers to the current region, the current address and the end of
081   * the region.  The regionCursor class maintains these 3 pointers, while the
082   * subclasses ToCursor and FromCursor provide methods specific to the
083   * read and write pointers.
084   */
085  @Uninterruptible
086  private abstract static class RegionCursor {
087
088    /** Name of the cursor - for debugging messages */
089    private final String name;
090
091    /**
092     * The current region, or zero if the cursor is invalid (eg after advancing
093     * past the end of the current work list
094     */
095    protected Address region;
096
097    /**
098     * The limit of the current region. When reading a populated region, this is the
099     * address of the last used byte.  When writing to a fresh region, this is the last
100     * byte in the region.
101     */
102    protected Address limit;
103
104    /** The current address */
105    protected Address cursor;
106
107    /**
108     * @param name The name of the region - for debugging messages.
109     */
110    RegionCursor(String name) {
111      this.name = name;
112    }
113
114    /**
115     * Hook to allow subclasses to initialize the cursor in different ways.
116     *
117     * @param region The region to be processed.
118     */
119    abstract void init(Address region);
120
121    /**
122     * Assert that the cursor is within the bounds of the region.  Calls to this
123     * must be guarded by {@code if (VM.VERIFY_ASSERTIONS)}
124     */
125    protected void assertCursorInBounds() {
126      VM.assertions._assert(!region.isZero());
127      VM.assertions._assert(cursor.GE(BumpPointer.getDataStart(region)),
128      "Cursor is below start of region");
129      VM.assertions._assert(cursor.LE(limit),"Cursor beyond end of region");
130    }
131
132    /**
133     * Increment the cursor.
134     * @param size Bytes to increment by
135     */
136    void inc(int size) {
137      this.cursor = cursor.plus(size);
138      if (VM.VERIFY_ASSERTIONS) assertCursorInBounds();
139    }
140
141    /**
142     * Increment the cursor to a specific address
143     * @param cursor Destination address
144     */
145    public void incTo(Address cursor) {
146      if (VM.VERIFY_ASSERTIONS) assertCursorInBounds();
147      if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(cursor.GE(this.cursor));
148      this.cursor = cursor;
149    }
150
151    /**
152     * @param other Other region
153     * @return {@code true} if this cursor points to the same region as {@code other}
154     */
155    boolean sameRegion(RegionCursor other) {
156      return region.EQ(other.getRegion());
157    }
158
159    /**
160     * @param size Size in bytes
161     * @return {@code true} if {@code size} bytes are available in the current region
162     */
163    boolean isAvailable(int size) {
164      return cursor.plus(size).LE(limit);
165    }
166
167    /**
168     * @return The current cursor
169     */
170    public Address get() {
171      return cursor;
172    }
173
174    /**
175     * @return The current region pointer
176     */
177    public Address getRegion() {
178      return region;
179    }
180
181    /**
182     * @return The current region limit
183     */
184    public Address getLimit() {
185      return limit;
186    }
187
188    /**
189     * Follow the linked-list of regions to the next region.
190     */
191    void advanceToNextRegion() {
192      Address nextRegion = MarkCompactLocal.getNextRegion(region);
193      if (nextRegion.isZero()) {
194        region = Address.zero();
195      } else {
196        init(nextRegion);
197        if (VM.VERIFY_ASSERTIONS) assertCursorInBounds();
198      }
199    }
200
201    /**
202     * @return {@code true} if we haven't advanced beyond the end of the region list
203     */
204    boolean isValid() {
205      return !region.isZero();
206    }
207
208    /**
209     * @param ref The object in question
210     * @return {@code true} if the object's start address is in this region
211     */
212    @Inline
213    boolean isInRegion(ObjectReference ref) {
214      Address addr = VM.objectModel.refToAddress(ref);
215      return addr.GE(BumpPointer.getDataStart(region)) && addr.LE(limit);
216    }
217
218    /**
219     * Print the cursor - for debugging
220     */
221    void print() {
222      Log.write(name); Log.write(" cursor:");
223      Log.write(" region="); Log.write(region);
224      Log.write(" limit="); Log.write(limit);
225      Log.write(" cursor="); Log.write(cursor);
226      Log.writeln();
227
228    }
229  }
230
231  /**
232   * Subclass for the read-only cursor that leads the scan of regions.
233   */
234  @Uninterruptible
235  private static final class FromCursor extends RegionCursor {
236    FromCursor() {
237      super("from");
238    }
239
240    /**
241     * Initialize the cursor - the limit is the end of the allocated data
242     */
243    @Override
244    void init(Address region) {
245      if (VM.VERIFY_ASSERTIONS) BumpPointer.checkRegionMetadata(region);
246      this.region = region;
247      this.cursor = MarkCompactLocal.getDataStart(region);
248      this.limit = MarkCompactLocal.getDataEnd(region);
249    }
250
251    /**
252     * Advance from the cursor to the start of the next object.
253     * @return The object reference of the next object.
254     */
255    @Inline
256    ObjectReference advanceToObject() {
257      ObjectReference current = VM.objectModel.getObjectFromStartAddress(cursor);
258      cursor = VM.objectModel.objectStartRef(current);
259      if (VM.VERIFY_ASSERTIONS) {
260        Address lowBound = BumpPointer.getDataStart(region);
261        VM.assertions._assert(cursor.GE(lowBound) && cursor.LE(limit),"Cursor outside region");
262      }
263      return current;
264    }
265
266    /**
267     * Advances the cursor to the end of the given object.
268     *
269     * @param current the object's reference
270     */
271    @Inline
272    void advanceToObjectEnd(ObjectReference current) {
273      cursor = VM.objectModel.getObjectEndAddress(current);
274      if (VM.VERIFY_ASSERTIONS) assertCursorInBounds();
275    }
276
277    /**
278     * Advance the cursor either to the next region in the list,
279     * or to a new region allocated from the global list.
280     * @param space the space that acts as the global list
281     */
282    void advanceToNextForwardableRegion(MarkCompactSpace space) {
283      if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(get().EQ(getLimit()));
284      Address nextRegion = BumpPointer.getNextRegion(region);
285      if (nextRegion.isZero()) {
286        nextRegion = space.getNextRegion();
287        if (nextRegion.isZero()) {
288          region = Address.zero();
289          return;
290        }
291        MarkCompactLocal.setNextRegion(region,nextRegion);
292        MarkCompactLocal.clearNextRegion(nextRegion);
293      }
294      init(nextRegion);
295      if (VM.VERIFY_ASSERTIONS) assertCursorInBounds();
296    }
297
298    /**
299     * Override the superclass with an additional assertion - we only advance
300     * when we have read to the end, and the cursor must point *precisely*
301     * to the last allocated byte in the region.
302     */
303    @Override
304    void advanceToNextRegion() {
305      if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(get().EQ(getLimit()));
306      super.advanceToNextRegion();
307    }
308
309    /**
310     * @return {@code true} if there are more objects in this region
311     */
312    boolean hasMoreObjects() {
313      return cursor.LT(limit);
314    }
315  }
316
317  /**
318   * Subclass for the read-only cursor that follows the 'from' cursor,
319   * writing or calculating the position of copied objects
320   */
321  @Uninterruptible
322  private static final class ToCursor extends RegionCursor {
323    ToCursor() {
324      super("to");
325    }
326
327    /**
328     * Initialize the cursor to a given region.  The limit is the limit of
329     * available space in the region.
330     */
331    @Override
332    void init(Address region) {
333      if (VM.VERIFY_ASSERTIONS) BumpPointer.checkRegionMetadata(region);
334      this.region = region;
335      this.cursor = MarkCompactLocal.getDataStart(region);
336      this.limit = MarkCompactLocal.getRegionLimit(region);
337      if (VM.VERIFY_ASSERTIONS) assertCursorInBounds();
338    }
339
340    /**
341     * Update the metadata of the current region with the current value
342     * of the cursor.  Zero the region from here to the end.
343     */
344    void finish() {
345      if (VM.VERIFY_ASSERTIONS) assertCursorInBounds();
346      Extent zeroBytes = limit.diff(cursor).toWord().toExtent();
347      VM.memory.zero(false, cursor, zeroBytes);
348      MarkCompactLocal.setDataEnd(region, cursor);
349      MarkCompactLocal.checkRegionMetadata(region);
350    }
351
352    /**
353     * Terminate the list of regions here.
354     * @return The address of the (old) next region in the list.
355     */
356    Address snip() {
357      Address nextRegion = BumpPointer.getNextRegion(region);
358      BumpPointer.clearNextRegion(region);
359      finish();
360      return nextRegion;
361    }
362
363    /**
364     * Copy an object to an address within this cursor's region.
365     * @param from The source object
366     * @param to The target object
367     */
368    @Inline
369    void copy(ObjectReference from, ObjectReference to) {
370      if (VM.VERIFY_ASSERTIONS) {
371        VM.assertions._assert(MarkCompactSpace.getForwardingPointer(from).toAddress().EQ(to.toAddress()));
372        VM.assertions._assert(cursor.GT(region) && cursor.LE(limit));
373      }
374      Address savedCursor = Address.zero();
375      if (VM.VERIFY_ASSERTIONS) savedCursor = cursor;
376      cursor = VM.objectModel.copyTo(from, to, cursor);
377      if (VM.VERIFY_ASSERTIONS) {
378        if (cursor.LT(BumpPointer.getDataStart(region)) || cursor.GT(limit)) {
379          Log.write("Copy of "); Log.write(from);
380          Log.write(" to "); Log.write(to);
381          Log.write(" puts cursor at "); Log.write(cursor);
382          Log.write(" (was: "); Log.write(savedCursor);
383          Log.writeln(")");
384        }
385        VM.assertions._assert(cursor.GT(region) && cursor.LE(limit));
386      }
387      MarkCompactSpace.setForwardingPointer(to, ObjectReference.nullReference());
388      if (VM.VERIFY_ASSERTIONS)
389        VM.assertions._assert(VM.objectModel.getObjectEndAddress(to).LE(limit));
390    }
391
392    /**
393     * Move to the next region, updating the metadata with the current 'write' state.
394     */
395    void finishAndAdvanceToNextRegion() {
396      finish();
397      advanceToNextRegion();
398    }
399
400    /**
401     * Move to the next region, in read-only mode.  Add the assertion of validity,
402     * since we shouldn't be able to fall off the end of the list while writing.
403     */
404    @Override
405    void advanceToNextRegion() {
406      super.advanceToNextRegion();
407      if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isValid());
408    }
409  }
410
411  /* ***************************************************************************************** */
412
413  /**
414   * Perform a linear scan through the objects allocated by this bump pointer,
415   * calculating where each live object will be post collection.<p>
416   *
417   * We maintain two cursors, {@code fromCursor} and {@code toCursor}, and simulate
418   * copying live objects from the former to the latter.  Initially, the cursors
419   * point to the first region in this collector's local list, and increment in
420   * lockstep until the first dead object is encountered.  After that, the to cursor
421   * trails the from cursor.<p>
422   *
423   * The outer loop advances the 'from' pointer
424   */
425  public void calculateForwardingPointers() {
426    if (regions.isZero()) {
427      regions = space.getNextRegion();
428    }
429
430    if (regions.isZero())
431      return;
432
433    fromCursor.init(regions);
434    toCursor.init(regions);
435
436    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(true);
437
438    /* Loop through active regions or until the last region */
439    while (fromCursor.isValid()) {
440      if (VERBOSE) {
441        fromCursor.print();
442        toCursor.print();
443      }
444
445      /* Loop through the objects in the current 'from' region */
446      while (fromCursor.hasMoreObjects()) {
447        ObjectReference current = fromCursor.advanceToObject();
448        fromCursor.advanceToObjectEnd(current);
449
450        if (MarkCompactSpace.toBeCompacted(current)) {
451          if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(MarkCompactSpace.getForwardingPointer(current).isNull());
452
453          // Fake - allocate it.
454          int size = VM.objectModel.getSizeWhenCopied(current);
455          int align = VM.objectModel.getAlignWhenCopied(current);
456          int offset = VM.objectModel.getAlignOffsetWhenCopied(current);
457          // Move to the (aligned) start of the next object
458          toCursor.incTo(Allocator.alignAllocationNoFill(toCursor.get(), align, offset));
459
460          /*
461           * If we're allocating into separate regions, and we've allocated beyond the end of the
462           * current region, advance to the next one.  We always allocate into regions we have
463           * scanned in this collector.
464           */
465          if (!toCursor.sameRegion(fromCursor) && !toCursor.isAvailable(size)) {
466            // The 'to' pointer always trails the 'from' pointer, guaranteeing that
467            // there's a next region to advance to.
468            toCursor.advanceToNextRegion();
469            toCursor.incTo(Allocator.alignAllocationNoFill(toCursor.get(), align, offset));
470          }
471
472          ObjectReference target = VM.objectModel.getReferenceWhenCopiedTo(current, toCursor.get());
473          if (toCursor.sameRegion(fromCursor) && target.toAddress().GE(current.toAddress())) {
474            // Don't move the object.
475            MarkCompactSpace.setForwardingPointer(current, current);
476            toCursor.incTo(VM.objectModel.getObjectEndAddress(current));
477          } else {
478            MarkCompactSpace.setForwardingPointer(current, target);
479            toCursor.inc(size);
480          }
481        }
482      }
483      fromCursor.advanceToNextForwardableRegion(space);
484    }
485  }
486
487
488  /**
489   * Perform the compacting phase of the collection.
490   */
491  public void compact() {
492    if (regions.isZero()) return;
493
494    toCursor.init(regions);
495    fromCursor.init(regions);
496
497    /* Loop through active regions or until the last region */
498    while (fromCursor.isValid()) {
499      if (VERBOSE) {
500        Log.write("Compacting from region "); Log.write(fromCursor.getRegion());
501        Log.write(" to region "); Log.writeln(toCursor.getRegion());
502      }
503
504      /* Loop through the objects in the region */
505      while (fromCursor.hasMoreObjects()) {
506        ObjectReference current = fromCursor.advanceToObject();
507        fromCursor.advanceToObjectEnd(current);
508
509        ObjectReference copyTo = MarkCompactSpace.getForwardingPointer(current);
510        if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!copyTo.toAddress().EQ(Address.fromIntZeroExtend(VM.ALIGNMENT_VALUE)));
511
512        if (!copyTo.isNull() && Space.isInSpace(MC.MARK_COMPACT, copyTo)) {
513          if (VM.VERIFY_ASSERTIONS) {
514            if (MarkCompactSpace.isMarked(current)) {
515              Log.write("Object "); Log.write(current);
516              Log.writeln(" is marked during the compact phase");
517              VM.objectModel.dumpObject(current);
518            }
519            VM.assertions._assert(!MarkCompactSpace.isMarked(current));
520          }
521          if (!toCursor.isInRegion(copyTo)) {
522            // Update metadata and move on
523            toCursor.finishAndAdvanceToNextRegion();
524          }
525          if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(toCursor.isInRegion(copyTo));
526          toCursor.copy(current, copyTo);
527          if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(toCursor.isInRegion(copyTo));
528          MarkCompactSpace.setForwardingPointer(copyTo, ObjectReference.nullReference());
529        }
530      }
531      fromCursor.advanceToNextRegion();
532    }
533
534    /* Fix up the last object pointer etc */
535    toCursor.finish();
536
537
538    /*
539     * Return unused pages to the global page resource
540     */
541    Address region = toCursor.snip();
542    while (!region.isZero()) {
543      Address nextRegion = MarkCompactLocal.getNextRegion(region);
544      space.release(region);
545      region = nextRegion;
546    }
547  }
548}