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.plan.refcount;
014
015 import org.mmtk.utility.Constants;
016 import org.mmtk.vm.VM;
017 import org.vmmagic.pragma.Inline;
018 import org.vmmagic.pragma.Uninterruptible;
019 import org.vmmagic.unboxed.ObjectReference;
020 import org.vmmagic.unboxed.Word;
021
022 @Uninterruptible
023 public class RCHeader implements Constants {
024
025 /* Requirements */
026 public static final int LOCAL_GC_BITS_REQUIRED = 0;
027 public static final int GLOBAL_GC_BITS_REQUIRED = 8;
028 public static final int GC_HEADER_WORDS_REQUIRED = 0;
029
030 /****************************************************************************
031 * Object Logging (applies to *all* objects)
032 */
033
034 /* Mask bits to signify the start/finish of logging an object */
035
036 /**
037 *
038 */
039 public static final int LOG_BIT = 0;
040 public static final Word LOGGED = Word.zero(); //...00000
041 public static final Word UNLOGGED = Word.one(); //...00001
042 public static final Word BEING_LOGGED = Word.one().lsh(2).minus(Word.one()); //...00011
043 public static final Word LOGGING_MASK = LOGGED.or(UNLOGGED).or(BEING_LOGGED); //...00011
044
045 /**
046 * Return <code>true</code> if <code>object</code> is yet to be logged (for
047 * coalescing RC).
048 *
049 * @param object The object in question
050 * @return <code>true</code> if <code>object</code> needs to be logged.
051 */
052 @Inline
053 @Uninterruptible
054 public static boolean logRequired(ObjectReference object) {
055 Word value = VM.objectModel.readAvailableBitsWord(object);
056 return value.and(LOGGING_MASK).EQ(UNLOGGED);
057 }
058
059 /**
060 * Attempt to log <code>object</code> for coalescing RC. This is
061 * used to handle a race to log the object, and returns
062 * <code>true</code> if we are to log the object and
063 * <code>false</code> if we lost the race to log the object.
064 *
065 * <p>If this method returns <code>true</code>, it leaves the object
066 * in the <code>BEING_LOGGED</code> state. It is the responsibility
067 * of the caller to change the object to <code>LOGGED</code> once
068 * the logging is complete.
069 *
070 * @see #makeLogged(ObjectReference)
071 * @param object The object in question
072 * @return <code>true</code> if the race to log
073 * <code>object</code>was won.
074 */
075 @Inline
076 @Uninterruptible
077 public static boolean attemptToLog(ObjectReference object) {
078 Word oldValue;
079 do {
080 oldValue = VM.objectModel.prepareAvailableBits(object);
081 if (oldValue.and(LOGGING_MASK).EQ(LOGGED)) {
082 return false;
083 }
084 } while ((oldValue.and(LOGGING_MASK).EQ(BEING_LOGGED)) ||
085 !VM.objectModel.attemptAvailableBits(object, oldValue, oldValue.or(BEING_LOGGED)));
086 if (VM.VERIFY_ASSERTIONS) {
087 Word value = VM.objectModel.readAvailableBitsWord(object);
088 VM.assertions._assert(value.and(LOGGING_MASK).EQ(BEING_LOGGED));
089 }
090 return true;
091 }
092
093
094 /**
095 * Signify completion of logging <code>object</code>.
096 *
097 * <code>object</code> is left in the <code>LOGGED</code> state.
098 *
099 * @see #attemptToLog(ObjectReference)
100 * @param object The object whose state is to be changed.
101 */
102 @Inline
103 @Uninterruptible
104 public static void makeLogged(ObjectReference object) {
105 Word value = VM.objectModel.readAvailableBitsWord(object);
106 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(value.and(LOGGING_MASK).NE(LOGGED));
107 VM.objectModel.writeAvailableBitsWord(object, value.and(LOGGING_MASK.not()));
108 }
109
110 /**
111 * Change <code>object</code>'s state to <code>UNLOGGED</code>.
112 *
113 * @param object The object whose state is to be changed.
114 */
115 @Inline
116 @Uninterruptible
117 public static void makeUnlogged(ObjectReference object) {
118 Word oldValue, newValue;
119 do {
120 oldValue = VM.objectModel.prepareAvailableBits(object);
121 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(oldValue.and(LOGGING_MASK).EQ(LOGGED));
122 newValue = oldValue.or(UNLOGGED);
123 } while(!VM.objectModel.attemptAvailableBits(object, oldValue, newValue));
124 }
125
126 /************************************************************************
127 * RC header word
128 */
129
130 /** The mark bit used for backup tracing. */
131 public static final int MARK_BIT = LOG_BIT + 2;
132 public static final Word MARK_BIT_MASK = Word.one().lsh(MARK_BIT);
133
134 /** The bit used for newly allocated objects. */
135 public static final int NEW_BIT = MARK_BIT + 1;
136 public static final Word NEW_BIT_MASK = Word.one().lsh(NEW_BIT);
137
138 /** Current not using any bits for cycle detection, etc */
139 public static final int BITS_USED = NEW_BIT + 1;
140
141 /* Reference counting increments */
142
143 public static final int INCREMENT_SHIFT = BITS_USED;
144 public static final Word INCREMENT = Word.one().lsh(INCREMENT_SHIFT);
145 public static final Word DOUBLE_INCREMENT = INCREMENT.lsh(1);
146 public static final Word LIVE_THRESHOLD = INCREMENT;
147
148 /* Return values from decRC */
149
150 public static final int DEC_KILL = 0;
151 public static final int DEC_ALIVE = 1;
152
153 /* Return values from incRC */
154
155 public static final int INC_OLD = 0;
156 public static final int INC_NEW = 1;
157
158 /* Limited bit thresholds and masks */
159
160 public static final Word refSticky = Word.one().lsh(BITS_IN_BYTE - BITS_USED).minus(Word.one()).lsh(INCREMENT_SHIFT);
161 public static final int refStickyValue = refSticky.rshl(INCREMENT_SHIFT).toInt();
162 public static final Word WRITE_MASK = refSticky.not();
163 public static final Word READ_MASK = refSticky;
164
165 /**
166 * Has this object been marked by the most recent backup trace.
167 */
168 @Inline
169 public static boolean isMarked(ObjectReference object) {
170 return isHeaderMarked(VM.objectModel.readAvailableBitsWord(object));
171 }
172
173 /**
174 * Has this object been marked by the most recent backup trace.
175 */
176 @Inline
177 public static void clearMarked(ObjectReference object) {
178 Word oldValue, newValue;
179 do {
180 oldValue = VM.objectModel.prepareAvailableBits(object);
181 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isHeaderMarked(oldValue));
182 newValue = oldValue.and(MARK_BIT_MASK.not());
183 } while (!VM.objectModel.attemptAvailableBits(object, oldValue, newValue));
184 }
185
186 /**
187 * Has this object been marked by the most recent backup trace.
188 */
189 @Inline
190 private static boolean isHeaderMarked(Word header) {
191 return header.and(MARK_BIT_MASK).EQ(MARK_BIT_MASK);
192 }
193
194 /**
195 * Attempt to atomically mark this object. Return <code>true</code> if the mark was performed.
196 */
197 @Inline
198 public static boolean testAndMark(ObjectReference object) {
199 Word oldValue, newValue;
200 do {
201 oldValue = VM.objectModel.prepareAvailableBits(object);
202 if (isHeaderMarked(oldValue)) {
203 return false;
204 }
205 newValue = oldValue.or(MARK_BIT_MASK);
206 } while (!VM.objectModel.attemptAvailableBits(object, oldValue, newValue));
207 return true;
208 }
209
210 /**
211 * Has this object been marked as new.
212 */
213 @Inline
214 public static boolean isNew(ObjectReference object) {
215 return isHeaderNew(VM.objectModel.readAvailableBitsWord(object));
216 }
217
218 /**
219 * Has this object been marked as new.
220 */
221 @Inline
222 private static boolean isHeaderNew(Word header) {
223 return header.and(NEW_BIT_MASK).NE(NEW_BIT_MASK);
224 }
225
226 /**
227 * Perform any required initialization of the GC portion of the header.
228 *
229 * @param object the object
230 * @param initialInc start with a reference count of 1 (0 if <code>false</code>)
231 */
232 @Inline
233 public static void initializeHeader(ObjectReference object, boolean initialInc) {
234 Word existingValue = VM.objectModel.readAvailableBitsWord(object);
235 Word initialValue = existingValue.and(WRITE_MASK).or((initialInc)? INCREMENT : Word.zero());
236 VM.objectModel.writeAvailableBitsWord(object, initialValue);
237 }
238
239 /**
240 * Return <code>true</code> if given object is live
241 *
242 * @param object The object whose liveness is to be tested
243 * @return <code>true</code> if the object is alive
244 */
245 @Inline
246 @Uninterruptible
247 public static boolean isLiveRC(ObjectReference object) {
248 Word value = VM.objectModel.readAvailableBitsWord(object);
249 if (isStuck(value)) return true;
250 return value.and(READ_MASK).GE(LIVE_THRESHOLD);
251 }
252
253 /**
254 * Return the reference count for the object.
255 *
256 * @param object The object whose liveness is to be tested
257 * @return <code>true</code> if the object is alive
258 */
259 @Inline
260 @Uninterruptible
261 public static int getRC(ObjectReference object) {
262 Word value = VM.objectModel.readAvailableBitsWord(object);
263 if (isStuck(value)) return refStickyValue;
264 return value.and(READ_MASK).rshl(INCREMENT_SHIFT).toInt();
265 }
266
267 /**
268 * Increment the reference count of an object. Return either
269 * <code>INC_OLD</code> if the object is not new,
270 * <code>INC_NEW</code> if the object is new.
271 *
272 * @param object The object whose RC is to be incremented.
273 * @return <code>INC_OLD</code> if the object is not new,
274 * <code>INC_NEW</code> if the object is new.
275 */
276 @Inline
277 public static int incRC(ObjectReference object) {
278 Word oldValue, newValue;
279 int rtn;
280 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(RCBase.isRCObject(object));
281 do {
282 oldValue = VM.objectModel.prepareAvailableBits(object);
283 if (isStuck(oldValue)) return INC_OLD;
284 if (RCBase.BUILD_FOR_GENRC) {
285 newValue = oldValue.plus(INCREMENT);
286 rtn = INC_OLD;
287 } else {
288 if (isHeaderNew(oldValue)) {
289 newValue = oldValue.plus(DOUBLE_INCREMENT);
290 newValue = newValue.or(NEW_BIT_MASK);
291 rtn = INC_NEW;
292 } else {
293 newValue = oldValue.plus(INCREMENT);
294 rtn = INC_OLD;
295 }
296 }
297 } while (!VM.objectModel.attemptAvailableBits(object, oldValue, newValue));
298 return rtn;
299 }
300
301 /**
302 * Decrement the reference count of an object. Return either
303 * <code>DEC_KILL</code> if the count went to zero,
304 * <code>DEC_ALIVE</code> if the count did not go to zero.
305 *
306 * @param object The object whose RC is to be decremented.
307 * @return <code>DEC_KILL</code> if the count went to zero,
308 * <code>DEC_ALIVE</code> if the count did not go to zero.
309 */
310 @Inline
311 @Uninterruptible
312 public static int decRC(ObjectReference object) {
313 Word oldValue, newValue;
314 int rtn;
315 if (VM.VERIFY_ASSERTIONS) {
316 VM.assertions._assert(RCBase.isRCObject(object));
317 VM.assertions._assert(isLiveRC(object));
318 }
319 do {
320 oldValue = VM.objectModel.prepareAvailableBits(object);
321 if (isStuck(oldValue)) return DEC_ALIVE;
322 newValue = oldValue.minus(INCREMENT);
323 if (newValue.and(READ_MASK).LT(LIVE_THRESHOLD)) {
324 rtn = DEC_KILL;
325 } else {
326 rtn = DEC_ALIVE;
327 }
328 } while (!VM.objectModel.attemptAvailableBits(object, oldValue, newValue));
329 return rtn;
330 }
331
332 /**
333 * Initialize the reference count of an object. Return either
334 * <code>INC_OLD</code> if the object is not new,
335 * <code>INC_NEW</code> if the object is new.
336 *
337 * @param object The object whose RC is to be initialized.
338 * @return <code>INC_OLD</code> if the object is not new,
339 * <code>INC_NEW</code> if the object is new.
340 */
341 @Inline
342 public static int initRC(ObjectReference object) {
343 Word oldValue, newValue;
344 int rtn;
345 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(RCBase.isRCObject(object));
346 do {
347 oldValue = VM.objectModel.prepareAvailableBits(object);
348 newValue = oldValue.and(WRITE_MASK).or(INCREMENT);
349 if (RCBase.BUILD_FOR_GENRC) {
350 rtn = INC_OLD;
351 } else {
352 if (isHeaderNew(oldValue)) {
353 newValue = newValue.or(NEW_BIT_MASK);
354 rtn = INC_NEW;
355 } else {
356 rtn = INC_OLD;
357 }
358 }
359 } while (!VM.objectModel.attemptAvailableBits(object, oldValue, newValue));
360 return rtn;
361 }
362
363 /**
364 * Retain the reference count of an object. Return either
365 * <code>INC_OLD</code> if the object is not new,
366 * <code>INC_NEW</code> if the object is new.
367 *
368 * @param object The object whose RC is to be retained.
369 * @return <code>INC_OLD</code> if the object is not new,
370 * <code>INC_NEW</code> if the object is new.
371 */
372 @Inline
373 public static int remainRC(ObjectReference object) {
374 Word oldValue, newValue;
375 int rtn;
376 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(RCBase.isRCObject(object));
377 do {
378 oldValue = VM.objectModel.prepareAvailableBits(object);
379 newValue = oldValue;
380 if (RCBase.BUILD_FOR_GENRC) {
381 return INC_OLD;
382 } else {
383 if (isHeaderNew(oldValue)) {
384 newValue = newValue.or(NEW_BIT_MASK);
385 rtn = INC_NEW;
386 } else {
387 return INC_OLD;
388 }
389 }
390 } while (!VM.objectModel.attemptAvailableBits(object, oldValue, newValue));
391 return rtn;
392 }
393
394 /**
395 * Has this object been stuck
396 */
397 @Inline
398 private static boolean isStuck(Word value) {
399 return value.and(refSticky).EQ(refSticky);
400 }
401 }