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     */
013    package org.mmtk.policy;
014    
015    import org.mmtk.plan.markcompact.MC;
016    import org.mmtk.utility.Log;
017    import org.mmtk.utility.alloc.Allocator;
018    import org.mmtk.utility.alloc.BumpPointer;
019    import org.mmtk.vm.VM;
020    import org.vmmagic.pragma.Inline;
021    import org.vmmagic.pragma.Uninterruptible;
022    import org.vmmagic.unboxed.Address;
023    import org.vmmagic.unboxed.Extent;
024    import org.vmmagic.unboxed.ObjectReference;
025    
026    /**
027     * This class implements unsynchronized (local) per-collector-thread elements of a
028     * sliding mark-compact collector.<p>
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
046    public 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        public 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        public 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         * Advance the cursor to the end of the given object.
268         */
269        @Inline
270        void advanceToObjectEnd(ObjectReference current) {
271          cursor = VM.objectModel.getObjectEndAddress(current);
272          if (VM.VERIFY_ASSERTIONS) assertCursorInBounds();
273        }
274    
275        /**
276         * Advance the cursor either to the next region in the list,
277         * or to a new region allocated from the global list.
278         * @param space
279         */
280        void advanceToNextForwardableRegion(MarkCompactSpace space) {
281          if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(get().EQ(getLimit()));
282          Address nextRegion = BumpPointer.getNextRegion(region);
283          if (nextRegion.isZero()) {
284            nextRegion = space.getNextRegion();
285            if (nextRegion.isZero()) {
286              region = Address.zero();
287              return;
288            }
289            MarkCompactLocal.setNextRegion(region,nextRegion);
290            MarkCompactLocal.clearNextRegion(nextRegion);
291          }
292          init(nextRegion);
293          if (VM.VERIFY_ASSERTIONS) assertCursorInBounds();
294        }
295    
296        /**
297         * Override the superclass with an additional assertion - we only advance
298         * when we have read to the end, and the cursor must point *precisely*
299         * to the last allocated byte in the region.
300         */
301        @Override
302        void advanceToNextRegion() {
303          if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(get().EQ(getLimit()));
304          super.advanceToNextRegion();
305        }
306    
307        /**
308         * @return {@code true} if there are more objects in this region
309         */
310        boolean hasMoreObjects() {
311          return cursor.LT(limit);
312        }
313      }
314    
315      /**
316       * Subclass for the read-only cursor that follows the 'from' cursor,
317       * writing or calculating the position of copied objects
318       */
319      @Uninterruptible
320      private static final class ToCursor extends RegionCursor {
321        public ToCursor() {
322          super("to");
323        }
324    
325        /**
326         * Initialize the cursor to a given region.  The limit is the limit of
327         * available space in the region.
328         */
329        @Override
330        void init(Address region) {
331          if (VM.VERIFY_ASSERTIONS) BumpPointer.checkRegionMetadata(region);
332          this.region = region;
333          this.cursor = MarkCompactLocal.getDataStart(region);
334          this.limit = MarkCompactLocal.getRegionLimit(region);
335          if (VM.VERIFY_ASSERTIONS) assertCursorInBounds();
336        }
337    
338        /**
339         * Update the metadata of the current region with the current value
340         * of the cursor.  Zero the region from here to the end.
341         */
342        void finish() {
343          if (VM.VERIFY_ASSERTIONS) assertCursorInBounds();
344          Extent zeroBytes = limit.diff(cursor).toWord().toExtent();
345          VM.memory.zero(false, cursor, zeroBytes);
346          MarkCompactLocal.setDataEnd(region, cursor);
347          MarkCompactLocal.checkRegionMetadata(region);
348        }
349    
350        /**
351         * Terminate the list of regions here.
352         * @return The address of the (old) next region in the list.
353         */
354        Address snip() {
355          Address nextRegion = BumpPointer.getNextRegion(region);
356          BumpPointer.clearNextRegion(region);
357          finish();
358          return nextRegion;
359        }
360    
361        /**
362         * Copy an object to an address within this cursor's region.
363         * @param from The source object
364         * @param to The target object
365         */
366        @Inline
367        void copy(ObjectReference from, ObjectReference to) {
368          if (VM.VERIFY_ASSERTIONS) {
369            VM.assertions._assert(MarkCompactSpace.getForwardingPointer(from).toAddress().EQ(to.toAddress()));
370            VM.assertions._assert(cursor.GT(region) && cursor.LE(limit));
371          }
372          Address savedCursor = Address.zero();
373          if (VM.VERIFY_ASSERTIONS) savedCursor = cursor;
374          cursor = VM.objectModel.copyTo(from, to, cursor);
375          if (VM.VERIFY_ASSERTIONS) {
376            if (cursor.LT(BumpPointer.getDataStart(region)) || cursor.GT(limit)) {
377              Log.write("Copy of "); Log.write(from);
378              Log.write(" to "); Log.write(to);
379              Log.write(" puts cursor at "); Log.write(cursor);
380              Log.write(" (was: "); Log.write(savedCursor);
381              Log.writeln(")");
382            }
383            VM.assertions._assert(cursor.GT(region) && cursor.LE(limit));
384          }
385          MarkCompactSpace.setForwardingPointer(to, ObjectReference.nullReference());
386          if (VM.VERIFY_ASSERTIONS)
387            VM.assertions._assert(VM.objectModel.getObjectEndAddress(to).LE(limit));
388        }
389    
390        /**
391         * Move to the next region, updating the metadata with the current 'write' state.
392         */
393        void finishAndAdvanceToNextRegion() {
394          finish();
395          advanceToNextRegion();
396        }
397    
398        /**
399         * Move to the next region, in read-only mode.  Add the assertion of validity,
400         * since we shouldn't be able to fall off the end of the list while writing.
401         */
402        @Override
403        void advanceToNextRegion() {
404          super.advanceToNextRegion();
405          if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isValid());
406        }
407      }
408    
409      /* ***************************************************************************************** */
410    
411      /**
412       * Perform a linear scan through the objects allocated by this bump pointer,
413       * calculating where each live object will be post collection.<p>
414       *
415       * We maintain two cursors, {@code fromCursor} and {@code toCursor}, and simulate
416       * copying live objects from the former to the latter.  Initially, the cursors
417       * point to the first region in this collector's local list, and increment in
418       * lockstep until the first dead object is encountered.  After that, the to cursor
419       * trails the from cursor.<p>
420       *
421       * The outer loop advances the 'from' pointer
422       */
423      public void calculateForwardingPointers() {
424        if (regions.isZero()) {
425          regions = space.getNextRegion();
426        }
427    
428        if (regions.isZero())
429          return;
430    
431        fromCursor.init(regions);
432        toCursor.init(regions);
433    
434        if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(true);
435    
436        /* Loop through active regions or until the last region */
437        while (fromCursor.isValid()) {
438          if (VERBOSE) {
439            fromCursor.print();
440            toCursor.print();
441          }
442    
443          /* Loop through the objects in the current 'from' region */
444          while (fromCursor.hasMoreObjects()) {
445            ObjectReference current = fromCursor.advanceToObject();
446            fromCursor.advanceToObjectEnd(current);
447    
448            if (MarkCompactSpace.toBeCompacted(current)) {
449              if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(MarkCompactSpace.getForwardingPointer(current).isNull());
450    
451              // Fake - allocate it.
452              int size = VM.objectModel.getSizeWhenCopied(current);
453              int align = VM.objectModel.getAlignWhenCopied(current);
454              int offset = VM.objectModel.getAlignOffsetWhenCopied(current);
455              // Move to the (aligned) start of the next object
456              toCursor.incTo(Allocator.alignAllocationNoFill(toCursor.get(), align, offset));
457    
458              /*
459               * If we're allocating into separate regions, and we've allocated beyond the end of the
460               * current region, advance to the next one.  We always allocate into regions we have
461               * scanned in this collector.
462               */
463              if (!toCursor.sameRegion(fromCursor) && !toCursor.isAvailable(size)) {
464                // The 'to' pointer always trails the 'from' pointer, guaranteeing that
465                // there's a next region to advance to.
466                toCursor.advanceToNextRegion();
467                toCursor.incTo(Allocator.alignAllocationNoFill(toCursor.get(), align, offset));
468              }
469    
470              ObjectReference target = VM.objectModel.getReferenceWhenCopiedTo(current, toCursor.get());
471              if (toCursor.sameRegion(fromCursor) && target.toAddress().GE(current.toAddress())) {
472                // Don't move the object.
473                MarkCompactSpace.setForwardingPointer(current, current);
474                toCursor.incTo(VM.objectModel.getObjectEndAddress(current));
475              } else {
476                MarkCompactSpace.setForwardingPointer(current, target);
477                toCursor.inc(size);
478              }
479            }
480          }
481          fromCursor.advanceToNextForwardableRegion(space);
482        }
483      }
484    
485    
486      /**
487       * Perform the compacting phase of the collection.
488       */
489      public void compact() {
490        if (regions.isZero()) return;
491    
492        toCursor.init(regions);
493        fromCursor.init(regions);
494    
495        /* Loop through active regions or until the last region */
496        while (fromCursor.isValid()) {
497          if (VERBOSE) {
498            Log.write("Compacting from region "); Log.write(fromCursor.getRegion());
499            Log.write(" to region "); Log.writeln(toCursor.getRegion());
500          }
501    
502          /* Loop through the objects in the region */
503          while (fromCursor.hasMoreObjects()) {
504            ObjectReference current = fromCursor.advanceToObject();
505            fromCursor.advanceToObjectEnd(current);
506    
507            ObjectReference copyTo = MarkCompactSpace.getForwardingPointer(current);
508            if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!copyTo.toAddress().EQ(Address.fromIntZeroExtend(VM.ALIGNMENT_VALUE)));
509    
510            if (!copyTo.isNull() && Space.isInSpace(MC.MARK_COMPACT, copyTo)) {
511              if (VM.VERIFY_ASSERTIONS) {
512                if (MarkCompactSpace.isMarked(current)) {
513                  Log.write("Object "); Log.write(current);
514                  Log.writeln(" is marked during the compact phase");
515                  VM.objectModel.dumpObject(current);
516                }
517                VM.assertions._assert(!MarkCompactSpace.isMarked(current));
518              }
519              if (!toCursor.isInRegion(copyTo)) {
520                // Update metadata and move on
521                toCursor.finishAndAdvanceToNextRegion();
522              }
523              if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(toCursor.isInRegion(copyTo));
524              toCursor.copy(current, copyTo);
525              if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(toCursor.isInRegion(copyTo));
526              MarkCompactSpace.setForwardingPointer(copyTo, ObjectReference.nullReference());
527            }
528          }
529          fromCursor.advanceToNextRegion();
530        }
531    
532        /* Fix up the last object pointer etc */
533        toCursor.finish();
534    
535    
536        /*
537         * Return unused pages to the global page resource
538         */
539        Address region = toCursor.snip();
540        while (!region.isZero()) {
541          Address nextRegion = MarkCompactLocal.getNextRegion(region);
542          space.release(region);
543          region = nextRegion;
544        }
545      }
546    }