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.TraceLocal;
016 import org.mmtk.plan.TransitiveClosure;
017 import org.mmtk.utility.alloc.BumpPointer;
018 import org.mmtk.utility.heap.*;
019 import org.mmtk.utility.Constants;
020 import org.mmtk.utility.Log;
021
022 import org.mmtk.vm.Lock;
023 import org.mmtk.vm.VM;
024
025 import org.vmmagic.unboxed.*;
026 import org.vmmagic.pragma.*;
027
028 /**
029 * This class implements functionality for a simple sliding mark-compact
030 * space.
031 */
032 @Uninterruptible public final class MarkCompactSpace extends Space
033 implements Constants {
034
035 /****************************************************************************
036 *
037 * Class variables
038 */
039
040 /**
041 *
042 */
043 public static final int LOCAL_GC_BITS_REQUIRED = 1;
044 public static final int GLOBAL_GC_BITS_REQUIRED = 0;
045 public static final int GC_HEADER_WORDS_REQUIRED = 1;
046
047 private static final Word GC_MARK_BIT_MASK = Word.one();
048 private static final Offset FORWARDING_POINTER_OFFSET = VM.objectModel.GC_HEADER_OFFSET();
049
050 private static final Lock lock = VM.newLock("mcSpace");
051
052 /** The list of occupied regions */
053 private Address regionList = Address.zero();
054
055 // TODO - maintain a separate list of partially allocated regions
056 // for threads to allocate into immediately after a collection.
057
058 /****************************************************************************
059 *
060 * Instance variables
061 */
062
063 /****************************************************************************
064 *
065 * Initialization
066 */
067
068 /**
069 * The caller specifies the region of virtual memory to be used for
070 * this space. If this region conflicts with an existing space,
071 * then the constructor will fail.
072 *
073 * @param name The name of this space (used when printing error messages etc)
074 * @param vmRequest An object describing the virtual memory requested.
075 */
076 public MarkCompactSpace(String name, VMRequest vmRequest) {
077 super(name, true, false, true, vmRequest);
078 if (vmRequest.isDiscontiguous()) {
079 pr = new FreeListPageResource(this, 0);
080 } else {
081 pr = new FreeListPageResource(this, start, extent, 0);
082 }
083 }
084
085 /**
086 * Prepare for a collection
087 */
088 public void prepare() {
089 }
090
091 /**
092 * Release after a collection
093 */
094 public void release() {
095 // nothing to do
096 }
097
098
099 /**
100 * {@inheritDoc}<p>
101 *
102 * In this case we do nothing ecause we only release pages enmasse.
103 */
104 @Override
105 @Inline
106 public void release(Address start) {
107 ((FreeListPageResource)pr).releasePages(start);
108 }
109
110 /**
111 * Trace an object under a copying collection policy.
112 * If the object is already copied, the copy is returned.
113 * Otherwise, a copy is created and returned.
114 * In either case, the object will be marked on return.
115 *
116 * @param trace The trace being conducted.
117 * @param object The object to be forwarded.
118 * @return The forwarded object.
119 */
120 @Override
121 @Inline
122 public ObjectReference traceObject(TransitiveClosure trace, ObjectReference object) {
123 if (VM.VERIFY_ASSERTIONS)
124 VM.assertions._assert(false);
125 return null;
126 }
127
128 /**
129 * Trace an object under a copying collection policy.
130 * If the object is already copied, the copy is returned.
131 * Otherwise, a copy is created and returned.
132 * In either case, the object will be marked on return.
133 *
134 * @param trace The trace being conducted.
135 * @param object The object to be forwarded.
136 * @return The forwarded object.
137 */
138 @Inline
139 public ObjectReference traceMarkObject(TraceLocal trace, ObjectReference object) {
140 if (MarkCompactCollector.VERY_VERBOSE) {
141 Log.write("marking "); Log.write(object);
142 }
143 if (testAndMark(object)) {
144 trace.processNode(object);
145 } else if (!getForwardingPointer(object).isNull()) {
146 if (MarkCompactCollector.VERY_VERBOSE) {
147 Log.write(" -> "); Log.writeln(getForwardingPointer(object));
148 }
149 return getForwardingPointer(object);
150 }
151 if (MarkCompactCollector.VERY_VERBOSE) {
152 Log.writeln();
153 }
154 return object;
155 }
156
157 /**
158 * Trace an object under a copying collection policy.
159 * If the object is already copied, the copy is returned.
160 * Otherwise, a copy is created and returned.
161 * In either case, the object will be marked on return.
162 *
163 * @param trace The trace being conducted.
164 * @param object The object to be forwarded.
165 * @return The forwarded object.
166 */
167 @Inline
168 public ObjectReference traceForwardObject(TraceLocal trace, ObjectReference object) {
169 if (testAndClearMark(object)) {
170 trace.processNode(object);
171 }
172 ObjectReference newObject = getForwardingPointer(object);
173 if (MarkCompactCollector.VERY_VERBOSE) {
174 Log.write("forwarding "); Log.write(object);
175 Log.write(" -> "); Log.writeln(newObject);
176 }
177 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!newObject.isNull());
178 return getForwardingPointer(object);
179 }
180
181 @Override
182 public boolean isLive(ObjectReference object) {
183 return isMarked(object);
184 }
185
186 @Override
187 public boolean isReachable(ObjectReference object) {
188 return isMarked(object);
189 }
190
191
192 /****************************************************************************
193 *
194 * Header manipulation
195 */
196
197 /**
198 * Perform any required post-allocation initialization
199 *
200 * <i>Nothing to be done in this case</i>
201 *
202 * @param object the object ref to the storage to be initialized
203 */
204 @Inline
205 public void postAlloc(ObjectReference object) {
206 }
207
208 /**
209 * Non-atomic read of forwarding pointer
210 *
211 * @param object The object whose forwarding pointer is to be read
212 * @return The forwarding pointer stored in <code>object</code>'s
213 * header.
214 */
215 @Inline
216 public static ObjectReference getForwardingPointer(ObjectReference object) {
217 return object.toAddress().loadObjectReference(FORWARDING_POINTER_OFFSET);
218 }
219
220 /**
221 * Initialise the header of the object.
222 *
223 * @param object The object to initialise
224 */
225 @Inline
226 public void initializeHeader(ObjectReference object) {
227 // nothing to do
228 }
229
230 /**
231 * Used to mark boot image objects during a parallel scan of objects
232 * during GC.
233 *
234 * @param object The object to be marked
235 * @return {@code true} if marking was done.
236 */
237 @Inline
238 public static boolean testAndMark(ObjectReference object) {
239 Word oldValue;
240 do {
241 oldValue = VM.objectModel.prepareAvailableBits(object);
242 Word markBit = oldValue.and(GC_MARK_BIT_MASK);
243 if (!markBit.isZero()) return false;
244 } while (!VM.objectModel.attemptAvailableBits(object, oldValue,
245 oldValue.or(GC_MARK_BIT_MASK)));
246 return true;
247 }
248
249 /**
250 * Used to mark boot image objects during a parallel scan of objects
251 * during GC Returns true if marking was done.
252 *
253 * @param object The object to be marked
254 */
255 @Inline
256 public static boolean isMarked(ObjectReference object) {
257 Word oldValue = VM.objectModel.readAvailableBitsWord(object);
258 Word markBit = oldValue.and(GC_MARK_BIT_MASK);
259 return (!markBit.isZero());
260 }
261
262 /**
263 * Used to mark boot image objects during a parallel scan of objects
264 * during GC Returns true if marking was done.
265 *
266 * @param object The object to be marked
267 */
268 @Inline
269 private static boolean testAndClearMark(ObjectReference object) {
270 Word oldValue;
271 do {
272 oldValue = VM.objectModel.prepareAvailableBits(object);
273 Word markBit = oldValue.and(GC_MARK_BIT_MASK);
274 if (markBit.isZero()) return false;
275 } while (!VM.objectModel.attemptAvailableBits(object, oldValue,
276 oldValue.and(GC_MARK_BIT_MASK.not())));
277 return true;
278 }
279
280
281 /**
282 * Used to mark boot image objects during a parallel scan of objects
283 * during GC Returns true if marking was done.
284 *
285 * @param object The object to be marked
286 */
287 @Inline
288 public static boolean toBeCompacted(ObjectReference object) {
289 Word oldValue = VM.objectModel.readAvailableBitsWord(object);
290 Word markBit = oldValue.and(GC_MARK_BIT_MASK);
291 return !markBit.isZero() && getForwardingPointer(object).isNull();
292 }
293
294 /**
295 * Used to mark boot image objects during a parallel scan of objects
296 * during GC Returns true if marking was done.
297 *
298 * @param object The object to be marked
299 */
300 @Inline
301 public static void clearMark(ObjectReference object) {
302 Word oldValue = VM.objectModel.readAvailableBitsWord(object);
303 VM.objectModel.writeAvailableBitsWord(object, oldValue.and(GC_MARK_BIT_MASK.not()));
304 }
305
306 /**
307 * Non-atomic write of forwarding pointer word (assumption, thread
308 * doing the set has done attempt to forward and owns the right to
309 * copy the object)
310 *
311 * @param object The object whose forwarding pointer is to be set
312 * @param ptr The forwarding pointer to be stored in the object's
313 * forwarding word
314 */
315 @Inline
316 public static void setForwardingPointer(ObjectReference object,
317 ObjectReference ptr) {
318 object.toAddress().store(ptr.toAddress(), FORWARDING_POINTER_OFFSET);
319 }
320
321 /**
322 * Non-atomic clear of forwarding pointer word (assumption, thread
323 * doing the set has done attempt to forward and owns the right to
324 * copy the object)
325 *
326 * @param object The object whose forwarding pointer is to be set
327 */
328 @Inline
329 public static void clearForwardingPointer(ObjectReference object) {
330 object.toAddress().store(Address.zero(), FORWARDING_POINTER_OFFSET);
331 }
332
333 /**
334 * @return A region of this space that has net yet been compacted during
335 * the current collection
336 */
337 public Address getNextRegion() {
338 lock.acquire();
339 if (regionList.isZero()) {
340 lock.release();
341 return Address.zero();
342 }
343 Address result = regionList;
344 regionList = BumpPointer.getNextRegion(regionList);
345 BumpPointer.clearNextRegion(result);
346 lock.release();
347 return result;
348 }
349
350 /**
351 * Append a region or list of regions to the global list
352 * @param region
353 */
354 public void append(Address region) {
355 lock.acquire();
356 if (MarkCompactCollector.VERBOSE) {
357 Log.write("Appending region "); Log.write(region);
358 Log.writeln(" to global list");
359 }
360 if (regionList.isZero()) {
361 regionList = region;
362 } else {
363 appendRegion(regionList,region);
364 }
365 lock.release();
366 }
367
368 public static void appendRegion(Address listHead, Address region) {
369 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!listHead.isZero());
370 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!region.isZero());
371 Address cursor = listHead;
372 while (!BumpPointer.getNextRegion(cursor).isZero()) {
373 cursor = BumpPointer.getNextRegion(cursor);
374 }
375 BumpPointer.setNextRegion(cursor,region);
376 }
377 }