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.TransitiveClosure;
016 import org.mmtk.utility.heap.*;
017 import org.mmtk.utility.options.Options;
018 import org.mmtk.utility.options.MarkSweepMarkBits;
019 import org.mmtk.utility.options.EagerCompleteSweep;
020 import org.mmtk.utility.Constants;
021 import org.mmtk.utility.HeaderByte;
022
023 import org.mmtk.vm.VM;
024
025 import org.vmmagic.pragma.*;
026 import org.vmmagic.unboxed.*;
027
028 /**
029 * Each instance of this class corresponds to one mark-sweep *space*.
030 * Each of the instance methods of this class may be called by any
031 * thread (i.e. synchronization must be explicit in any instance or
032 * class method). This contrasts with the MarkSweepLocal, where
033 * instances correspond to *plan* instances and therefore to kernel
034 * threads. Thus unlike this class, synchronization is not necessary
035 * in the instance methods of MarkSweepLocal.
036 */
037 @Uninterruptible
038 public final class MarkSweepSpace extends SegregatedFreeListSpace implements Constants {
039
040 /****************************************************************************
041 *
042 * Class variables
043 */
044
045 /**
046 * Select between using mark bits in a side bitmap, or mark bits
047 * in the headers of object (or other sub-class scheme), and a single
048 * mark bit per block.
049 */
050 public static final boolean HEADER_MARK_BITS = VM.config.HEADER_MARK_BITS;
051 /** highest bit bits we may use */
052 private static final int AVAILABLE_LOCAL_BITS = 8 - HeaderByte.USED_GLOBAL_BITS;
053
054 /* mark bits */
055 private static final int COUNT_BASE = 0;
056
057 public static final int DEFAULT_MARKCOUNT_BITS = 4;
058 public static final int MAX_MARKCOUNT_BITS = AVAILABLE_LOCAL_BITS - COUNT_BASE;
059 private static final byte MARK_COUNT_INCREMENT = (byte) (1<<COUNT_BASE);
060 private static final byte MARK_COUNT_MASK = (byte) (((1<<MAX_MARKCOUNT_BITS)-1) << COUNT_BASE);
061
062 private static final boolean EAGER_MARK_CLEAR = HeaderByte.NEEDS_UNLOGGED_BIT;
063
064 /* header requirements */
065 public static final int LOCAL_GC_BITS_REQUIRED = MAX_MARKCOUNT_BITS;
066 public static final int GLOBAL_GC_BITS_REQUIRED = 0;
067 public static final int GC_HEADER_WORDS_REQUIRED = 0;
068
069
070 /****************************************************************************
071 *
072 * Instance variables
073 */
074
075 /**
076 *
077 */
078 private byte markState = 1;
079 private byte allocState = 0;
080 private boolean inMSCollection;
081 private static final boolean usingStickyMarkBits = VM.activePlan.constraints().needsLogBitInHeader(); /* are sticky mark bits in use? */
082 private boolean isAgeSegregated = false; /* is this space a nursery space? */
083 private boolean isAllocAsMarked = false;
084
085 /****************************************************************************
086 *
087 * Initialization
088 */
089
090 static {
091 Options.markSweepMarkBits = new MarkSweepMarkBits();
092 Options.eagerCompleteSweep = new EagerCompleteSweep();
093 }
094
095 /**
096 * The caller specifies the region of virtual memory to be used for
097 * this space. If this region conflicts with an existing space,
098 * then the constructor will fail.
099 *
100 * @param name The name of this space (used when printing error messages etc)
101 * @param vmRequest An object describing the virtual memory requested.
102 */
103 public MarkSweepSpace(String name, VMRequest vmRequest) {
104 super(name, 0, vmRequest);
105 if (usingStickyMarkBits) allocState |= HeaderByte.UNLOGGED_BIT;
106 }
107
108 /**
109 * This instance will be age-segregated using the sticky mark bits
110 * algorithm. Perform appropriate initialization
111 */
112 public void makeAgeSegregatedSpace() {
113 /* we must be using sticky mark bits */
114 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(usingStickyMarkBits);
115 allocState &= ~HeaderByte.UNLOGGED_BIT; /* clear the unlogged bit for nursery allocs */
116 isAgeSegregated = true;
117 }
118
119 /**
120 * Should SegregatedFreeListSpace manage a side bitmap to keep track of live objects?
121 */
122 @Override
123 @Inline
124 protected boolean maintainSideBitmap() {
125 return !HEADER_MARK_BITS;
126 }
127
128 @Override
129 @Inline
130 protected boolean preserveFreeList() {
131 return !LAZY_SWEEP;
132 }
133
134 /****************************************************************************
135 *
136 * Allocation
137 */
138
139 /**
140 * Prepare the next block in the free block list for use by the free
141 * list allocator. In the case of lazy sweeping this involves
142 * sweeping the available cells. <b>The sweeping operation must
143 * ensure that cells are pre-zeroed</b>, as this method must return
144 * pre-zeroed cells.
145 *
146 * @param block The block to be prepared for use
147 * @param sizeClass The size class of the block
148 * @return The address of the first pre-zeroed cell in the free list
149 * for this block, or zero if there are no available cells.
150 */
151 @Override
152 protected Address advanceToBlock(Address block, int sizeClass) {
153 if (HEADER_MARK_BITS) {
154 if (inMSCollection) markBlock(block);
155 }
156
157 if (LAZY_SWEEP) {
158 return makeFreeList(block, sizeClass);
159 } else {
160 return getFreeList(block);
161 }
162 }
163
164 /**
165 * {@inheritDoc}<p>
166 *
167 * This is to ensure that appropriate collection state can be initialized
168 * for the block.
169 */
170 @Override
171 protected void notifyNewBlock(Address block, int sizeClass) {
172 if (HEADER_MARK_BITS) {
173 if (inMSCollection) markBlock(block);
174 }
175 }
176
177 /****************************************************************************
178 *
179 * Collection
180 */
181
182 /**
183 * Prepare for a new collection increment. For the mark-sweep
184 * collector we must flip the state of the mark bit between
185 * collections.
186 *
187 * @param gcWholeMS True if we are going to collect the whole marksweep space
188 */
189 public void prepare(boolean gcWholeMS) {
190 if (HEADER_MARK_BITS && Options.eagerCompleteSweep.getValue()) {
191 consumeBlocks();
192 } else {
193 flushAvailableBlocks();
194 }
195 if (HEADER_MARK_BITS) {
196 if (gcWholeMS) {
197 allocState = markState;
198 if (usingStickyMarkBits && !isAgeSegregated) /* if true, we allocate as "mature", not nursery */
199 allocState |= HeaderByte.UNLOGGED_BIT;
200 markState = deltaMarkState(true);
201 if (EAGER_MARK_CLEAR)
202 clearAllBlockMarks();
203 }
204 } else {
205 zeroLiveBits();
206 }
207 inMSCollection = true;
208 }
209
210 /**
211 * A new collection increment has completed. For the mark-sweep
212 * collector this means we can perform the sweep phase.
213 */
214 public void release() {
215 sweepConsumedBlocks(!EAGER_MARK_CLEAR);
216 inMSCollection = false;
217 }
218
219 /**
220 * Release an allocated page or pages
221 *
222 * @param start The address of the start of the page or pages
223 */
224 @Override
225 @Inline
226 public void release(Address start) {
227 ((FreeListPageResource) pr).releasePages(start);
228 }
229
230 /**
231 * Should the sweep reclaim the cell containing this object. Is this object
232 * live. This is only used when maintainSideBitmap is false.
233 *
234 * @param object The object to query
235 * @return True if the cell should be reclaimed
236 */
237 @Override
238 @Inline
239 protected boolean isCellLive(ObjectReference object) {
240 if (!HEADER_MARK_BITS) {
241 return super.isCellLive(object);
242 }
243 return testMarkState(object);
244 }
245
246 /****************************************************************************
247 *
248 * Object processing and tracing
249 */
250
251 /**
252 * Trace a reference to an object under a mark sweep collection
253 * policy. If the object header is not already marked, mark the
254 * object in either the bitmap or by moving it off the treadmill,
255 * and enqueue the object for subsequent processing. The object is
256 * marked as (an atomic) side-effect of checking whether already
257 * marked.
258 *
259 * @param object The object to be traced.
260 * @return The object (there is no object forwarding in this
261 * collector, so we always return the same object: this could be a
262 * void method but for compliance to a more general interface).
263 */
264 @Override
265 @Inline
266 public ObjectReference traceObject(TransitiveClosure trace, ObjectReference object) {
267 if (HEADER_MARK_BITS) {
268 if (testAndMark(object)) {
269 markBlock(object);
270 trace.processNode(object);
271 }
272 } else {
273 if (testAndSetLiveBit(object)) {
274 trace.processNode(object);
275 }
276 }
277 return object;
278 }
279
280 /**
281 * @return {@code true} if this object is known to be live (i.e. it is marked)
282 */
283 @Override
284 @Inline
285 public boolean isLive(ObjectReference object) {
286 if (HEADER_MARK_BITS) {
287 return testMarkState(object);
288 } else {
289 return liveBitSet(object);
290 }
291 }
292
293 /**
294 * Get the previous mark state.
295 *
296 * @return The previous mark state.
297 */
298 @Inline
299 public byte getPreviousMarkState() {
300 return deltaMarkState(false);
301 }
302
303 /**
304 * Return the mark state incremented or decremented by one.
305 *
306 * @param increment If true, then return the incremented value else return the decremented value
307 * @return the mark state incremented or decremented by one.
308 */
309 private byte deltaMarkState(boolean increment) {
310 byte mask = (byte) (((1 << Options.markSweepMarkBits.getValue()) - 1)<<COUNT_BASE);
311 byte rtn = (byte) (increment ? markState + MARK_COUNT_INCREMENT : markState - MARK_COUNT_INCREMENT);
312 rtn &= mask;
313 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((markState & ~MARK_COUNT_MASK) == 0);
314 return rtn;
315 }
316
317 /****************************************************************************
318 *
319 * Header manipulation
320 */
321
322 /**
323 * Perform any required post allocation initialization
324 *
325 * @param object the object ref to the storage to be initialized
326 */
327 @Inline
328 public void postAlloc(ObjectReference object) {
329 initializeHeader(object, true);
330 }
331
332 /**
333 * Perform any required post copy (i.e. in-GC allocation) initialization.
334 * This is relevant (for example) when MS is used as the mature space in
335 * a copying GC.
336 *
337 * @param object the object ref to the storage to be initialized
338 * @param majorGC Is this copy happening during a major gc?
339 */
340 @Inline
341 public void postCopy(ObjectReference object, boolean majorGC) {
342 initializeHeader(object, false);
343 if (!HEADER_MARK_BITS) {
344 testAndSetLiveBit(object);
345 }
346 }
347
348 /**
349 * Perform any required initialization of the GC portion of the header.
350 *
351 * @param object the object ref to the storage to be initialized
352 * @param alloc is this initialization occuring due to (initial) allocation
353 * (true) or due to copying (false)?
354 */
355 @Inline
356 public void initializeHeader(ObjectReference object, boolean alloc) {
357 if (HEADER_MARK_BITS) {
358 byte oldValue = VM.objectModel.readAvailableByte(object);
359 byte newValue = (byte) ((oldValue & ~MARK_COUNT_MASK) | (alloc && !isAllocAsMarked ? allocState : markState));
360 VM.objectModel.writeAvailableByte(object, newValue);
361 } else if (HeaderByte.NEEDS_UNLOGGED_BIT)
362 HeaderByte.markAsUnlogged(object);
363 }
364
365 /**
366 * Atomically attempt to set the mark bit of an object. Return true
367 * if successful, false if the mark bit was already set.
368 *
369 * @param object The object whose mark bit is to be set
370 */
371 @Inline
372 private boolean testAndMark(ObjectReference object) {
373 byte oldValue, markBits, newValue;
374 oldValue = VM.objectModel.readAvailableByte(object);
375 markBits = (byte) (oldValue & MARK_COUNT_MASK);
376 if (markBits == markState) return false;
377 newValue = (byte)((oldValue & ~MARK_COUNT_MASK) | markState);
378 if (HeaderByte.NEEDS_UNLOGGED_BIT) newValue |= HeaderByte.UNLOGGED_BIT;
379 VM.objectModel.writeAvailableByte(object, newValue);
380 return true;
381 }
382
383 /**
384 * Return true if the mark count for an object has the given value.
385 *
386 * @param object The object whose mark bit is to be tested
387 * @return <code>true</code> if the mark bit for the object is set.
388 */
389 @Inline
390 private boolean testMarkState(ObjectReference object) {
391 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((markState & ~MARK_COUNT_MASK) == 0);
392 return (VM.objectModel.readAvailableByte(object) & MARK_COUNT_MASK) == markState;
393 }
394
395 public void makeAllocAsMarked() {
396 isAllocAsMarked = true;
397 }
398 }