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.immix;
014
015 import static org.mmtk.policy.immix.ImmixConstants.*;
016
017 import org.mmtk.plan.Plan;
018 import org.mmtk.plan.TransitiveClosure;
019 import org.mmtk.policy.Space;
020 import org.mmtk.utility.heap.*;
021 import org.mmtk.utility.options.LineReuseRatio;
022 import org.mmtk.utility.options.Options;
023 import org.mmtk.utility.Constants;
024 import org.mmtk.utility.ForwardingWord;
025 import org.mmtk.utility.HeaderByte;
026 import org.mmtk.utility.Log;
027
028 import org.mmtk.vm.Lock;
029 import org.mmtk.vm.VM;
030
031 import org.vmmagic.pragma.*;
032 import org.vmmagic.unboxed.*;
033
034 /**
035 * Each instance of this class corresponds to one immix *space*.
036 * Each of the instance methods of this class may be called by any
037 * thread (i.e. synchronization must be explicit in any instance or
038 * class method). This contrasts with the SquishLocal, where
039 * instances correspond to *plan* instances and therefore to kernel
040 * threads. Thus unlike this class, synchronization is not necessary
041 * in the instance methods of SquishLocal.
042 *
043 */
044 @Uninterruptible
045 public final class ImmixSpace extends Space implements Constants {
046
047 /****************************************************************************
048 *
049 * Class variables
050 */
051 private static short reusableMarkStateThreshold = 0;
052
053 /****************************************************************************
054 *
055 * Instance variables
056 */
057 private byte markState = ObjectHeader.MARK_BASE_VALUE;
058 byte lineMarkState = RESET_LINE_MARK_STATE;
059 private byte lineUnavailState = RESET_LINE_MARK_STATE;
060 private boolean inCollection;
061 private int linesConsumed = 0;
062
063 private Lock mutatorLock = VM.newLock(getName()+"mutator");
064 private Lock gcLock = VM.newLock(getName()+"gc");
065
066 private Address allocBlockCursor = Address.zero();
067 private Address allocBlockSentinel = Address.zero();
068 private boolean exhaustedReusableSpace = true;
069
070 private final ChunkList chunkMap = new ChunkList();
071 private final Defrag defrag;
072
073 /****************************************************************************
074 *
075 * Initialization
076 */
077
078 static {
079 Options.lineReuseRatio = new LineReuseRatio();
080 reusableMarkStateThreshold = (short) (Options.lineReuseRatio.getValue() * MAX_BLOCK_MARK_STATE);
081 }
082
083 /**
084 * The caller specifies the region of virtual memory to be used for
085 * this space. If this region conflicts with an existing space,
086 * then the constructor will fail.
087 *
088 * @param name The name of this space (used when printing error messages etc)
089 * @param pageBudget The number of pages this space may consume before consulting the plan
090 * @param vmRequest The virtual memory request
091 */
092 public ImmixSpace(String name, int pageBudget, VMRequest vmRequest) {
093 super(name, false, false, vmRequest);
094 if (vmRequest.isDiscontiguous())
095 pr = new FreeListPageResource(pageBudget, this, Chunk.getRequiredMetaDataPages());
096 else
097 pr = new FreeListPageResource(pageBudget, this, start, extent, Chunk.getRequiredMetaDataPages());
098 defrag = new Defrag((FreeListPageResource) pr);
099 }
100
101 /****************************************************************************
102 *
103 * Global prepare and release
104 */
105
106 /**
107 * Prepare for a new collection increment.
108 */
109 public void prepare(boolean majorGC) {
110 if (majorGC) {
111 markState = ObjectHeader.deltaMarkState(markState, true);
112 lineMarkState++;
113 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(lineMarkState <= MAX_LINE_MARK_STATE);
114 }
115 chunkMap.reset();
116 defrag.prepare(chunkMap, this);
117 inCollection = true;
118
119 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(VM.activePlan.collectorCount() <= MAX_COLLECTORS);
120 }
121
122 /**
123 * A new collection increment has completed. Release global resources.
124 * @param majorGC TODO
125 */
126 public boolean release(boolean majorGC) {
127 boolean didDefrag = defrag.inDefrag();
128 if (majorGC) {
129 if (lineMarkState == MAX_LINE_MARK_STATE)
130 lineMarkState = RESET_LINE_MARK_STATE;
131 lineUnavailState = lineMarkState;
132 }
133 chunkMap.reset();
134 defrag.globalRelease();
135 inCollection = false;
136
137 /* set up reusable space */
138 if (allocBlockCursor.isZero()) allocBlockCursor = chunkMap.getHeadChunk();
139 allocBlockSentinel = allocBlockCursor;
140 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isRecycleAllocChunkAligned(allocBlockSentinel));
141 exhaustedReusableSpace = allocBlockCursor.isZero();
142 if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() >= 9) {
143 Log.write("gr[allocBlockCursor: "); Log.write(allocBlockCursor); Log.write(" allocBlockSentinel: "); Log.write(allocBlockSentinel); Log.writeln("]");
144 }
145
146 /* really just want this to happen once after options are booted, but no harm in re-doing it */
147 reusableMarkStateThreshold = (short) (Options.lineReuseRatio.getValue() * MAX_BLOCK_MARK_STATE);
148 Defrag.defragReusableMarkStateThreshold = (short) (Options.defragLineReuseRatio.getValue() * MAX_BLOCK_MARK_STATE);
149
150 linesConsumed = 0;
151 return didDefrag;
152 }
153
154 /**
155 * Determine the collection kind.
156 *
157 * @param emergencyCollection Is this collection an emergency (last did not yield enough)?
158 * @param collectWholeHeap Is this a whole heap collection?
159 * @param collectionAttempt Which attempt is this to collect?
160 * @param collectionTrigger What is triggering the collection?
161 */
162 public void decideWhetherToDefrag(boolean emergencyCollection, boolean collectWholeHeap, int collectionAttempt, int collectionTrigger) {
163 defrag.decideWhetherToDefrag(emergencyCollection, collectWholeHeap, collectionAttempt, collectionTrigger, exhaustedReusableSpace);
164 }
165
166 /****************************************************************************
167 *
168 * Collection state access methods
169 */
170
171 /**
172 * Return true if this space is currently being collected.
173 *
174 * @return True if this space is currently being collected.
175 */
176 @Inline
177 public boolean inImmixCollection() {
178 return inCollection;
179 }
180
181 /**
182 * Return true if this space is currently being defraged.
183 *
184 * @return True if this space is currently being defraged.
185 */
186 @Inline
187 public boolean inImmixDefragCollection() {
188 return inCollection && defrag.inDefrag();
189 }
190
191 /**
192 * Return the number of pages allocated since the last collection
193 *
194 * @return The number of pages allocated since the last collection
195 */
196 public int getPagesAllocated() {
197 return linesConsumed>>(LOG_BYTES_IN_PAGE-LOG_BYTES_IN_LINE);
198 }
199
200 /**
201 * Return the reusable mark state threshold, which determines how
202 * eagerly lines should be recycled (by default these values are
203 * set so that all lines are recycled).
204 *
205 * @param forDefrag The query is the context of a defragmenting collection
206 * @return The reusable mark state threshold
207 */
208 @Inline
209 public static short getReusuableMarkStateThreshold(boolean forDefrag) {
210 return forDefrag ? Defrag.defragReusableMarkStateThreshold : reusableMarkStateThreshold;
211 }
212
213 /****************************************************************************
214 *
215 * Allocation
216 */
217
218 /**
219 * Return a pointer to a set of new usable blocks, or null if none are available.
220 * Use different block selection heuristics depending on whether the allocation
221 * request is "hot" or "cold".
222 *
223 * @param hot True if the requesting context is for hot allocations (used for
224 * allocations from high allocation volume sites).
225 * @return The pointer into the alloc table containing usable blocks.
226 */
227 public Address getSpace(boolean hot, boolean copy, int lineUseCount) {
228 Address rtn;
229 if (copy)
230 defrag.getBlock();
231
232 linesConsumed += lineUseCount;
233
234 rtn = acquire(PAGES_IN_BLOCK);
235
236 if (VM.VERIFY_ASSERTIONS) {
237 VM.assertions._assert(Block.isAligned(rtn));
238 VM.assertions._assert(!(copy && Block.isDefragSource(rtn)));
239 }
240
241 if (!rtn.isZero()) {
242 Block.setBlockAsInUse(rtn);
243 Chunk.updateHighWater(rtn);
244 if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() >= 9) {
245 Log.write("gs["); Log.write(rtn); Log.write(" -> "); Log.write(rtn.plus(BYTES_IN_BLOCK-1)); Log.write(" copy: "); Log.write(copy); Log.writeln("]");
246 }
247 }
248
249 return rtn;
250 }
251
252 /**
253 * This hook is called by page resources each time a space grows. The space may
254 * tap into the hook to monitor heap growth. The call is made from within the
255 * page resources' critical region, immediately before yielding the lock.
256 *
257 * @param start The start of the newly allocated space
258 * @param bytes The size of the newly allocated space
259 * @param newChunk True if the new space encroached upon or started a new chunk or chunks.
260 */
261 @Override
262 public void growSpace(Address start, Extent bytes, boolean newChunk) {
263 super.growSpace(start, bytes, newChunk);
264 if (newChunk) {
265 Address chunk = chunkAlign(start.plus(bytes), true);
266 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(chunkAlign(start.plus(bytes), true).EQ(chunk));
267 Chunk.clearMetaData(chunk);
268 chunkMap.addNewChunkToMap(chunk);
269 }
270 }
271
272 public Address acquireReusableBlocks() {
273 if (VM.VERIFY_ASSERTIONS) {
274 VM.assertions._assert(isRecycleAllocChunkAligned(allocBlockCursor));
275 VM.assertions._assert(isRecycleAllocChunkAligned(allocBlockSentinel));
276 }
277 Address rtn;
278
279 lock();
280 if (exhaustedReusableSpace)
281 rtn = Address.zero();
282 else {
283 rtn = allocBlockCursor;
284 Address lastAllocChunk = chunkAlign(allocBlockCursor, true);
285 allocBlockCursor = allocBlockCursor.plus(BYTES_IN_RECYCLE_ALLOC_CHUNK);
286 if (allocBlockCursor.GT(Chunk.getHighWater(lastAllocChunk)))
287 allocBlockCursor = chunkMap.nextChunk(lastAllocChunk);
288 if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() >= 9) {
289 Log.write("arb[ rtn: "); Log.write(rtn); Log.write(" allocBlockCursor: "); Log.write(allocBlockCursor); Log.write(" allocBlockSentinel: "); Log.write(allocBlockSentinel); Log.writeln("]");
290 }
291
292 if (allocBlockCursor.isZero() || allocBlockCursor.EQ(allocBlockSentinel)) {
293 exhaustedReusableSpace = true;
294 if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() >= 9) {
295 Log.writeln("[Reusable space exhausted]");
296 }
297 }
298 }
299 unlock();
300 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isRecycleAllocChunkAligned(rtn));
301 return rtn;
302 }
303
304 /**
305 * Release a block. A block is free, so call the underlying page allocator
306 * to release the associated storage.
307 *
308 * @param block The address of the block to be released
309 */
310 @Inline
311 public void release(Address block) {
312 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(Block.isAligned(block));
313 Block.setBlockAsUnallocated(block);
314 ((FreeListPageResource) pr).releasePages(block);
315 }
316
317 /**
318 * Release one or more contiguous chunks associated with a discontiguous
319 * space. This hook is called by the page level allocators whenever a
320 * complete discontiguous chunk is released.
321 *
322 * @param chunk THe address of the start of the contiguous chunk or chunks
323 * @return The number of chunks freed
324 */
325 @Override
326 public int releaseDiscontiguousChunks(Address chunk) {
327 chunkMap.removeChunkFromMap(chunk);
328 return super.releaseDiscontiguousChunks(chunk);
329 }
330
331 /****************************************************************************
332 *
333 * Header manipulation
334 */
335
336 /**
337 * Perform any required post allocation initialization
338 *
339 * @param object the object ref to the storage to be initialized
340 */
341 @Inline
342 public void postAlloc(ObjectReference object, int bytes) {
343 if (bytes > BYTES_IN_LINE)
344 ObjectHeader.markAsStraddling(object);
345 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(ObjectHeader.isNewObject(object));
346 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!ForwardingWord.isForwardedOrBeingForwarded(object));
347 }
348
349 /**
350 * Perform any required post copy (i.e. in-GC allocation) initialization.
351 * This is relevant (for example) when Squish is used as the mature space in
352 * a copying GC.
353 *
354 * @param object the object ref to the storage to be initialized
355 * @param majorGC Is this copy happening during a major gc?
356 */
357 @Inline
358 public void postCopy(ObjectReference object, int bytes, boolean majorGC) {
359 ObjectHeader.writeMarkState(object, markState, bytes > BYTES_IN_LINE);
360 if (!MARK_LINE_AT_SCAN_TIME && majorGC) markLines(object);
361 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!ForwardingWord.isForwardedOrBeingForwarded(object));
362 if (VM.VERIFY_ASSERTIONS && HeaderByte.NEEDS_UNLOGGED_BIT) VM.assertions._assert(HeaderByte.isUnlogged(object));
363 }
364
365 /****************************************************************************
366 *
367 * Object tracing
368 */
369
370 /**
371 * Trace a reference to an object. If the object header is not already
372 * marked, mark the object and enqueue it for subsequent processing.
373 *
374 * @param trace The trace performing the transitive closure
375 * @param object The object to be traced.
376 * @param allocator The allocator to which any copying should be directed
377 * @return The object, which may have been moved.
378 */
379 @Inline
380 public ObjectReference traceObject(TransitiveClosure trace, ObjectReference object, int allocator) {
381 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(defrag.determined(true));
382
383 ObjectReference rtn = object;
384 if (isDefragSource(object))
385 rtn = traceObjectWithOpportunisticCopy(trace, object, allocator, false);
386 else
387 traceObjectWithoutMoving(trace, object);
388
389 if (VM.VERIFY_ASSERTIONS) {
390 VM.assertions._assert(!rtn.isNull());
391 VM.assertions._assert(defrag.spaceExhausted() || !isDefragSource(rtn) || (ObjectHeader.isPinnedObject(rtn)));
392 }
393 return rtn;
394 }
395
396 /**
397 * Trace a reference to an object in the context of a non-moving collection. This
398 * call is optimized for the simpler non-moving case.
399 *
400 * @param trace The trace performing the transitive closure
401 * @param object The object to be traced.
402 * @return The object (there is no object forwarding in this
403 * trace method, so we always return the same object: this could be a
404 * void method but for compliance to a more general interface).
405 */
406 @Inline
407 public ObjectReference fastTraceObject(TransitiveClosure trace, ObjectReference object) {
408 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(defrag.determined(false));
409 traceObjectWithoutMoving(trace, object);
410 return object;
411 }
412
413 /**
414 * Trace a reference to an object during a nursery collection for
415 * a sticky mark bits implementation of immix. If the object header
416 * is not already marked, mark the object and enqueue it for subsequent
417 * processing.
418 *
419 * @param trace The trace performing the transitive closure
420 * @param object The object to be traced.
421 * @param allocator The allocator to which any copying should be directed
422 * @return Either the object or a forwarded object, depending on
423 * the policy in place.
424 */
425 @Inline
426 public ObjectReference nurseryTraceObject(TransitiveClosure trace, ObjectReference object, int allocator) {
427 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!defrag.inDefrag());
428 if (TMP_PREFER_COPY_ON_NURSERY_GC)
429 return traceObjectWithOpportunisticCopy(trace, object, allocator, true);
430 else
431 return fastTraceObject(trace, object);
432 }
433
434 /**
435 * Trace a reference to an object. This interface is not supported by immix, since
436 * we require the allocator to be identified except for the special case of the fast
437 * trace.
438 *
439 * @param trace The trace performing the transitive closure
440 * @param object The object to be traced.
441 * @return null and fail.
442 */
443 public ObjectReference traceObject(TransitiveClosure trace, ObjectReference object) {
444 VM.assertions.fail("unsupported interface");
445 return null;
446 }
447
448 /**
449 * Trace a reference to an object in the context of a non-moving collection. This
450 * call is optimized for the simpler non-moving case.
451 *
452 * @param trace The trace performing the transitive closure
453 * @param object The object to be traced.
454 */
455 @Inline
456 private void traceObjectWithoutMoving(TransitiveClosure trace, ObjectReference object) {
457 byte markValue = markState;
458 byte oldMarkState = ObjectHeader.testAndMark(object, markValue);
459 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!defrag.inDefrag() || defrag.spaceExhausted() || !isDefragSource(object));
460 if (oldMarkState != markValue) {
461 if (!MARK_LINE_AT_SCAN_TIME)
462 markLines(object);
463 trace.processNode(object);
464 }
465 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!ForwardingWord.isForwardedOrBeingForwarded(object));
466 if (VM.VERIFY_ASSERTIONS && HeaderByte.NEEDS_UNLOGGED_BIT) VM.assertions._assert(HeaderByte.isUnlogged(object));
467 }
468
469 /**
470 * Trace a reference to an object, forwarding the object if appropriate
471 * If the object is not already marked, mark the object and enqueue it
472 * for subsequent processing.
473 *
474 * @param trace The trace performing the transitive closure
475 * @param object The object to be traced.
476 * @param allocator The allocator to which any copying should be directed
477 * @return Either the object or a forwarded object, if it was forwarded.
478 */
479 @Inline
480 private ObjectReference traceObjectWithOpportunisticCopy(TransitiveClosure trace, ObjectReference object, int allocator, boolean nurseryCollection) {
481 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(nurseryCollection || (defrag.determined(true) && isDefragSource(object)));
482
483 /* now race to be the (potential) forwarder */
484 Word priorStatusWord = ForwardingWord.attemptToForward(object);
485 if (ForwardingWord.stateIsForwardedOrBeingForwarded(priorStatusWord)) {
486 /* We lost the race; the object is either forwarded or being forwarded by another thread. */
487 /* Note that the concurrent attempt to forward the object may fail, so the object may remain in-place */
488 ObjectReference rtn = ForwardingWord.spinAndGetForwardedObject(object, priorStatusWord);
489 if (VM.VERIFY_ASSERTIONS && rtn == object) VM.assertions._assert((nurseryCollection && ObjectHeader.testMarkState(object, markState)) || defrag.spaceExhausted() || ObjectHeader.isPinnedObject(object));
490 if (VM.VERIFY_ASSERTIONS && rtn != object) VM.assertions._assert(nurseryCollection || !isDefragSource(rtn));
491 if (VM.VERIFY_ASSERTIONS && HeaderByte.NEEDS_UNLOGGED_BIT) VM.assertions._assert(HeaderByte.isUnlogged(rtn));
492 return rtn;
493 } else {
494 byte priorState = (byte) (priorStatusWord.toInt() & 0xFF);
495 /* the object is unforwarded, either because this is the first thread to reach it, or because the object can't be forwarded */
496 if (ObjectHeader.testMarkState(priorState, markState)) {
497 /* the object has not been forwarded, but has the correct mark state; unlock and return unmoved object */
498 /* Note that in a sticky mark bits collector, the mark state does not change at each GC, so correct mark state does not imply another thread got there first */
499 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(nurseryCollection || defrag.spaceExhausted() || ObjectHeader.isPinnedObject(object));
500 ObjectHeader.returnToPriorStateAndEnsureUnlogged(object, priorState); // return to uncontested state
501 if (VM.VERIFY_ASSERTIONS && Plan.NEEDS_LOG_BIT_IN_HEADER) VM.assertions._assert(HeaderByte.isUnlogged(object));
502 return object;
503 } else {
504 /* we are the first to reach the object; either mark in place or forward it */
505 ObjectReference newObject;
506 if (ObjectHeader.isPinnedObject(object) || defrag.spaceExhausted()) {
507 /* mark in place */
508 ObjectHeader.setMarkStateUnlogAndUnlock(object, priorState, markState);
509 newObject = object;
510 if (VM.VERIFY_ASSERTIONS && Plan.NEEDS_LOG_BIT_IN_HEADER) VM.assertions._assert(HeaderByte.isUnlogged(newObject));
511 } else {
512 /* forward */
513 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!ObjectHeader.isPinnedObject(object));
514 newObject = ForwardingWord.forwardObject(object, allocator);
515 if (VM.VERIFY_ASSERTIONS && Plan.NEEDS_LOG_BIT_IN_HEADER) VM.assertions._assert(HeaderByte.isUnlogged(newObject));
516 }
517 if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() >= 9) {
518 Log.write("C["); Log.write(object); Log.write("/");
519 Log.write(getName()); Log.write("] -> ");
520 Log.write(newObject); Log.write("/");
521 Log.write(Space.getSpaceForObject(newObject).getName());
522 Log.writeln("]");
523 }
524 if (!MARK_LINE_AT_SCAN_TIME)
525 markLines(newObject);
526 trace.processNode(newObject);
527 if (VM.VERIFY_ASSERTIONS) {
528 if (!((getSpaceForObject(newObject) != this) ||
529 (newObject == object) ||
530 (nurseryCollection && willNotMoveThisNurseryGC(newObject)) ||
531 (defrag.inDefrag() && willNotMoveThisGC(newObject))
532 )) {
533 Log.write(" object: "); Log.writeln(object);
534 Log.write("newObject: "); Log.writeln(newObject);
535 Log.write(" space: "); Log.writeln(getName());
536 Log.write(" nursery?: "); Log.writeln(nurseryCollection);
537 Log.write(" mature?: "); Log.writeln(ObjectHeader.isMatureObject(object));
538 Log.write(" wnmngc?: "); Log.writeln(willNotMoveThisNurseryGC(newObject));
539 Log.write(" pinned?: "); Log.writeln(ObjectHeader.isPinnedObject(object));
540 Space otherSpace = getSpaceForObject(newObject);
541 Log.write(" space(o): "); Log.writeln(otherSpace == null ? "<NULL>" : otherSpace.getName());
542 VM.assertions._assert(false);
543 }
544 }
545 return newObject;
546 }
547 }
548 }
549
550 /**
551 * Mark the line/s associated with a given object. This is distinct from the
552 * above tracing code because line marks are stored separately from the
553 * object headers (thus both must be set), and also because we found empirically
554 * that it was more efficient to perform the line mark of the object during
555 * the scan phase (which occurs after the trace phase), presumably because
556 * the latency of the associated memory operations was better hidden in the
557 * context of that code
558 *
559 * @param object The object which is live and for which the associated lines
560 * must be marked.
561 */
562 public void markLines(ObjectReference object) {
563 Address address = VM.objectModel.objectStartRef(object);
564 Line.mark(address, lineMarkState);
565 if (ObjectHeader.isStraddlingObject(object))
566 Line.markMultiLine(address, object, lineMarkState);
567 }
568
569 public int getNextUnavailableLine(Address baseLineAvailAddress, int line) {
570 return Line.getNextUnavailable(baseLineAvailAddress, line, lineUnavailState);
571 }
572
573 public int getNextAvailableLine(Address baseLineAvailAddress, int line) {
574 return Line.getNextAvailable(baseLineAvailAddress, line, lineUnavailState);
575 }
576
577 /****************************************************************************
578 *
579 * Establish available lines
580 */
581
582 /**
583 * Establish the number of recyclable lines lines available for allocation
584 * during defragmentation, populating the spillAvailHistogram, which buckets
585 * available lines according to the number of holes on the block on which
586 * the available lines reside.
587 *
588 * @param spillAvailHistogram A histogram of availability to be populated
589 * @return The number of available recyclable lines
590 */
591 int getAvailableLines(int[] spillAvailHistogram) {
592 int availableLines;
593 if (allocBlockCursor.isZero() || exhaustedReusableSpace) {
594 availableLines = 0;
595 } else {
596 if (allocBlockCursor.EQ(allocBlockSentinel)) {
597 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!exhaustedReusableSpace);
598 allocBlockCursor = chunkMap.getHeadChunk();
599 allocBlockSentinel = allocBlockCursor;
600 }
601 availableLines = getUsableLinesInRegion(allocBlockCursor, allocBlockSentinel, spillAvailHistogram);
602 }
603 return availableLines;
604 }
605
606 /**
607 * Return the number of lines usable for allocation during defragmentation in the
608 * address range specified by start and end. Populate a histogram to indicate where
609 * the usable lines reside as a function of block hole count.
610 *
611 * @param start The start of the region to be checked for availability
612 * @param end The end of the region to be checked for availability
613 * @param spillAvailHistogram The histogram which will be populated
614 * @return The number of usable lines
615 */
616 private int getUsableLinesInRegion(Address start, Address end, int[] spillAvailHistogram) {
617 int usableLines = 0;
618 Address blockCursor = Chunk.isAligned(start) ? start.plus(Chunk.FIRST_USABLE_BLOCK_INDEX<<LOG_BYTES_IN_BLOCK) : start;
619 Address blockStateCursor = Block.getBlockMarkStateAddress(blockCursor);
620 Address chunkCursor = Chunk.align(blockCursor);
621 if (Chunk.getByteOffset(end) < Chunk.FIRST_USABLE_BLOCK_INDEX<<LOG_BYTES_IN_BLOCK)
622 end = Chunk.align(end).plus(Chunk.FIRST_USABLE_BLOCK_INDEX<<LOG_BYTES_IN_BLOCK);
623
624 for (int i = 0; i <= MAX_CONSV_SPILL_COUNT; i++) spillAvailHistogram[i] = 0;
625
626 Address highwater = Chunk.getHighWater(chunkCursor);
627 do {
628 short markState = blockStateCursor.loadShort();
629 if (markState != 0 && markState <= reusableMarkStateThreshold) {
630 int usable = LINES_IN_BLOCK - markState;
631 short bucket = (short) Block.getConservativeSpillCount(blockCursor);
632 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(bucket >= 0 && bucket <= MAX_CONSV_SPILL_COUNT);
633 spillAvailHistogram[bucket] += usable;
634 usableLines += usable;
635 }
636 blockCursor = blockCursor.plus(BYTES_IN_BLOCK);
637 if (blockCursor.GT(highwater)) {
638 chunkCursor = chunkMap.nextChunk(chunkCursor);
639 if (chunkCursor.isZero()) break;
640 blockCursor = chunkCursor.plus(Chunk.FIRST_USABLE_BLOCK_INDEX<<LOG_BYTES_IN_BLOCK);
641 blockStateCursor = Block.getBlockMarkStateAddress(blockCursor);
642 highwater = Chunk.getHighWater(chunkCursor);
643 } else
644 blockStateCursor = blockStateCursor.plus(Block.BYTES_IN_BLOCK_STATE_ENTRY);
645 } while (blockCursor.NE(end));
646
647 return usableLines;
648 }
649
650 /****************************************************************************
651 *
652 * Object state
653 */
654
655 /**
656 * Generic test of the liveness of an object
657 *
658 * @param object The object in question
659 * @return True if this object is known to be live (i.e. it is marked)
660 */
661 @Inline
662 public boolean isLive(ObjectReference object) {
663 if (defrag.inDefrag() && isDefragSource(object))
664 return ForwardingWord.isForwardedOrBeingForwarded(object) || ObjectHeader.testMarkState(object, markState);
665 else
666 return ObjectHeader.testMarkState(object, markState);
667 }
668
669 /**
670 * Test the liveness of an object during copying sticky mark bits collection
671 *
672 * @param object The object in question
673 * @return True if this object is known to be live (i.e. it is marked)
674 */
675 @Inline
676 public boolean copyNurseryIsLive(ObjectReference object) {
677 return ForwardingWord.isForwardedOrBeingForwarded(object) || ObjectHeader.testMarkState(object, markState);
678 }
679
680 /**
681 * Test the liveness of an object during defragmentation
682 *
683 * @param object The object in question
684 * @return True if this object is known to be live (i.e. it is marked)
685 */
686 @Inline
687 public boolean fastIsLive(ObjectReference object) {
688 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!defrag.inDefrag());
689 return ObjectHeader.testMarkState(object, markState);
690 }
691
692 @Inline
693 public boolean willNotMoveThisGC(ObjectReference object) {
694 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(getSpaceForObject(object) == this && defrag.inDefrag());
695 return ObjectHeader.isPinnedObject(object) || willNotMoveThisGC(VM.objectModel.refToAddress(object));
696 }
697
698 @Inline
699 public boolean willNotMoveThisNurseryGC(ObjectReference object) {
700 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(getSpaceForObject(object) == this);
701 return ObjectHeader.isMatureObject(object);
702 }
703
704 @Inline
705 private boolean isDefragSource(ObjectReference object) {
706 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(getSpaceForObject(object) == this);
707 return isDefragSource(VM.objectModel.refToAddress(object));
708 }
709
710 @Inline
711 public boolean willNotMoveThisGC(Address address) {
712 return !defrag.inDefrag() || defrag.spaceExhausted() || !isDefragSource(address);
713 }
714
715 @Inline
716 public boolean isDefragSource(Address address) {
717 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(getSpaceForObject(address.toObjectReference()) == this);
718 return Block.isDefragSource(address);
719 }
720
721
722 /****************************************************************************
723 *
724 * Locks
725 */
726
727 /**
728 * Acquire the appropriate lock depending on whether the context is
729 * GC or mutator.
730 */
731 private void lock() {
732 if (inCollection)
733 gcLock.acquire();
734 else
735 mutatorLock.acquire();
736 }
737
738 /**
739 * Release the appropriate lock depending on whether the context is
740 * GC or mutator.
741 */
742 private void unlock() {
743 if (inCollection)
744 gcLock.release();
745 else
746 mutatorLock.release();
747 }
748
749
750 /****************************************************************************
751 *
752 * Misc
753 */
754 public static boolean isRecycleAllocChunkAligned(Address ptr) {
755 return ptr.toWord().and(RECYCLE_ALLOC_CHUNK_MASK).EQ(Word.zero());
756 }
757
758 ChunkList getChunkMap() { return chunkMap; }
759 Defrag getDefrag() { return defrag; }
760 }