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.utility.sanitychecker;
014
015import static org.mmtk.utility.Constants.BYTES_IN_WORD;
016
017import org.mmtk.plan.TraceLocal;
018import org.mmtk.policy.RawPageSpace;
019import org.mmtk.utility.deque.*;
020import org.mmtk.utility.SimpleHashtable;
021
022import org.vmmagic.pragma.*;
023import org.vmmagic.unboxed.*;
024
025/**
026 * This class implements a simple hashtable to store and retrieve per
027 * object information for sanity checking. <p>
028 *
029 * This class is not thread safe.
030 */
031@Uninterruptible
032public final class SanityDataTable extends SimpleHashtable {
033
034  /** The number of bits for the normal reference count */
035  private static final int NORMAL_RC_BITS = 25;
036
037  /** The mask for the normal reference count */
038  private static final int NORMAL_RC_MASK = (1 << 25) - 1;
039
040  /** The shift for the root reference count */
041  private static final int ROOT_RC_SHIFT = NORMAL_RC_BITS;
042
043  /** The increment to use for normal increments */
044  private static final int NORMAL_RC_INC = 1;
045
046  /** The increment to use for root increments */
047  private static final int ROOT_RC_INC = 1 << ROOT_RC_SHIFT;
048
049  /**
050   * Create a new data table of a specified size.
051   *
052   * @param rps The space to acquire the data structure from.
053   * @param logSize The log of the number of table entries.
054   */
055  public SanityDataTable(RawPageSpace rps, int logSize) {
056    super(rps, logSize, Extent.fromIntSignExtend(BYTES_IN_WORD));
057  }
058
059  /**
060   * Increment the data word for an object.
061   *
062   * @param entry The table entry.
063   * @param root True if this is a root reference.
064   * @return True if this is the first ref to that object.
065   */
066  @Inline
067  public static boolean incRC(Address entry, boolean root) {
068    Address data = SimpleHashtable.getPayloadAddress(entry);
069    int old = data.loadInt();
070    data.store(old + (root ? ROOT_RC_INC : NORMAL_RC_INC));
071    return (old == 0);
072  }
073
074  /**
075   * Push any entries that are only in this table, and not the
076   * passed table. This does not compare values.
077   *
078   * @param other The table to use for comparison.
079   * @param deque The buffer to push results onto.
080   */
081  public void pushNotInOther(SanityDataTable other,
082                             ObjectReferenceDeque deque) {
083    Address entry = getFirst();
084    while (!entry.isZero()) {
085      Word key = SimpleHashtable.getKey(entry);
086      if (!other.contains(key)) {
087        deque.push(key.toAddress().toObjectReference());
088      }
089      entry = getNext(entry);
090    }
091  }
092
093
094  /**
095   * Given an address of an entry, read the reference count,
096   * excluding root references.
097   *
098   * @param entry The entry
099   * @return The reference count.
100   */
101  public static int getNormalRC(Address entry) {
102    return SimpleHashtable.getPayloadAddress(entry).loadInt() & NORMAL_RC_MASK;
103  }
104
105  /**
106   * Given an address of an entry, read the root reference count.
107   *
108   * @param entry The entry
109   * @return The root reference count.
110   */
111  public static int getRootRC(Address entry) {
112    return SimpleHashtable.getPayloadAddress(entry).loadInt() >>> ROOT_RC_SHIFT;
113  }
114
115  /**
116   * Given an address of an entry, read the total reference count.
117   *
118   * @param entry The entry
119   * @return The total reference count.
120   */
121  public static int getRC(Address entry) {
122    int val = SimpleHashtable.getPayloadAddress(entry).loadInt();
123    return (val & NORMAL_RC_MASK) + val >>> ROOT_RC_SHIFT;
124  }
125
126  /**
127   * Given an address of an entry, read the reference component.
128   *
129   * @param entry The entry
130   * @return The object reference.
131   */
132  public static ObjectReference getObjectReference(Address entry) {
133    return SimpleHashtable.getKey(entry).toAddress().toObjectReference();
134  }
135
136  /**
137   * Forward data table using the supplied trace. Note that the data is
138   * not hashed correctly, so only enumeration can be used without
139   * rehashing.
140   *
141   * @param trace The trace to use.
142   */
143  public void forwardTable(TraceLocal trace) {
144    Address entry = getFirst();
145    while (!entry.isZero()) {
146      ObjectReference obj = getObjectReference(entry);
147      SimpleHashtable.replaceKey(entry, trace.getForwardedReference(obj).toAddress().toWord());
148      entry = getNext(entry);
149    }
150  }
151
152  /**
153   * Get an entry for an object.
154   *
155   * @param object The object to find an entry for.
156   * @param create Create an entry if none exists?
157   * @return The entry address.
158   */
159  public Address getEntry(ObjectReference object, boolean create) {
160    return super.getEntry(object.toAddress().toWord(), create);
161  }
162}