Source code

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