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 }