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 }