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.policy.immix;
014
015import static org.mmtk.policy.immix.ImmixConstants.*;
016import static org.mmtk.utility.Constants.LOG_BYTES_IN_SHORT;
017
018import org.mmtk.vm.VM;
019import org.vmmagic.pragma.Uninterruptible;
020import org.vmmagic.unboxed.Address;
021import org.vmmagic.unboxed.Extent;
022import org.vmmagic.unboxed.Offset;
023
024/**
025 * This class defines operations over block-granularity meta-data
026 *
027 */
028@Uninterruptible
029public class Block  {
030
031  static Address align(final Address ptr) {
032    return ptr.toWord().and(BLOCK_MASK.not()).toAddress();
033  }
034
035  public static boolean isAligned(final Address address) {
036    return address.EQ(align(address));
037  }
038
039  private static int getChunkIndex(final Address block) {
040    return block.toWord().and(CHUNK_MASK).rshl(LOG_BYTES_IN_BLOCK).toInt();
041  }
042
043  /***************************************************************************
044   * Block marking
045   */
046
047
048  /**
049   * @param address the block's address
050   * @return whether the block is unallocated
051   */
052  public static boolean isUnused(final Address address) {
053    return getBlockMarkState(address) == UNALLOCATED_BLOCK_STATE;
054  }
055
056  static boolean isUnusedState(Address cursor) {
057    return cursor.loadShort() == UNALLOCATED_BLOCK_STATE;
058  }
059
060  static short getMarkState(Address cursor) {
061    return cursor.loadShort();
062  }
063
064  static void setState(Address cursor, short value) {
065    cursor.store(value);
066  }
067
068  public static short getBlockMarkState(Address address) {
069    return getBlockMarkStateAddress(address).loadShort();
070  }
071
072  static void setBlockAsInUse(Address address) {
073    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isUnused(address));
074    setBlockState(address, UNMARKED_BLOCK_STATE);
075  }
076
077  public static void setBlockAsReused(Address address) {
078    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!isUnused(address));
079    setBlockState(address, REUSED_BLOCK_STATE);
080  }
081
082  static void setBlockAsUnallocated(Address address) {
083    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!isUnused(address));
084    getBlockMarkStateAddress(address).store(UNALLOCATED_BLOCK_STATE);
085  }
086
087  private static void setBlockState(Address address, short value) {
088    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(value != UNALLOCATED_BLOCK_STATE);
089    getBlockMarkStateAddress(address).store(value);
090  }
091
092  static Address getBlockMarkStateAddress(Address address) {
093    Address chunk = Chunk.align(address);
094    int index = getChunkIndex(address);
095    Address rtn = chunk.plus(Chunk.BLOCK_STATE_TABLE_OFFSET).plus(index << LOG_BYTES_IN_BLOCK_STATE_ENTRY);
096    if (VM.VERIFY_ASSERTIONS) {
097      Address block = chunk.plus(index << LOG_BYTES_IN_BLOCK);
098      VM.assertions._assert(isAligned(block));
099      boolean valid = rtn.GE(chunk.plus(Chunk.BLOCK_STATE_TABLE_OFFSET)) && rtn.LT(chunk.plus(Chunk.BLOCK_STATE_TABLE_OFFSET + BLOCK_STATE_TABLE_BYTES));
100      VM.assertions._assert(valid);
101    }
102    return rtn;
103  }
104
105  /***************************************************************************
106   * Sweeping
107   */
108
109  /**
110   * Sweeps one block.<p>
111   *
112   * TODO: needs better documentation.
113   *
114   * @param block the block's address
115   * @param markHistogram the mark histogram
116   * @param markState the mark value
117   * @param resetMarkState whether to reset the mark state
118   * @return number of marked lines
119   */
120  static short sweepOneBlock(Address block, int[] markHistogram, final byte markState, final boolean resetMarkState) {
121    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isAligned(block));
122
123    final boolean unused = isUnused(block);
124    if (unused && !SANITY_CHECK_LINE_MARKS)
125      return 0;
126
127    Address markTable = Line.getBlockMarkTable(block);
128
129    short markCount = 0;
130    short conservativeSpillCount = 0;
131    byte mark, lastMark = 0;
132    for (int offset = 0; offset < (LINES_IN_BLOCK << Line.LOG_BYTES_IN_LINE_STATUS); offset += Line.BYTES_IN_LINE_STATUS) {
133       if (VM.VERIFY_ASSERTIONS) {
134        VM.assertions._assert(markTable.plus(offset).GE(Chunk.align(block).plus(Chunk.LINE_MARK_TABLE_OFFSET)));
135        VM.assertions._assert(markTable.plus(offset).LT(Chunk.align(block).plus(Chunk.LINE_MARK_TABLE_OFFSET + Line.LINE_MARK_TABLE_BYTES)));
136      }
137      mark = markTable.loadByte(Offset.fromIntZeroExtend(offset));
138      if (resetMarkState)
139        markTable.store(mark == markState ? RESET_LINE_MARK_STATE : 0, Offset.fromIntZeroExtend(offset));
140
141      if (mark == markState)
142        markCount++;
143      else if (lastMark == markState)
144        conservativeSpillCount++;
145      else if (SANITY_CHECK_LINE_MARKS && lastMark != markState) {
146        VM.memory.zero(false, block.plus(offset << (LOG_BYTES_IN_LINE - Line.LOG_BYTES_IN_LINE_STATUS)),Extent.fromIntZeroExtend(BYTES_IN_LINE));
147      }
148
149      lastMark = mark;
150    }
151    if (VM.VERIFY_ASSERTIONS) {
152      VM.assertions._assert(markCount <= LINES_IN_BLOCK);
153      VM.assertions._assert(markCount + conservativeSpillCount <= LINES_IN_BLOCK);
154      VM.assertions._assert(markCount == 0 || !isUnused(block));
155    }
156
157    getDefragStateAddress(block).store(conservativeSpillCount);
158    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(markCount >= conservativeSpillCount);
159    markHistogram[conservativeSpillCount] += markCount;
160
161    markCount = (short) (markCount + conservativeSpillCount);
162
163    return markCount;
164  }
165
166  /****************************************************************************
167   * Block defrag state
168   */
169
170  /**
171   * @param address the block's address
172   * @return whether the defrag state is {@link #BLOCK_IS_DEFRAG_SOURCE}
173   */
174  public static boolean isDefragSource(Address address) {
175    return getDefragStateAddress(address).loadShort() == BLOCK_IS_DEFRAG_SOURCE;
176  }
177
178  static void clearConservativeSpillCount(Address address) {
179    getDefragStateAddress(address).store((short) 0);
180  }
181
182  static short getConservativeSpillCount(Address address) {
183    return getDefragStateAddress(address).loadShort();
184  }
185
186  static Address getDefragStateAddress(Address address) {
187    Address chunk = Chunk.align(address);
188    int index = getChunkIndex(address);
189    Address rtn = chunk.plus(Chunk.BLOCK_DEFRAG_STATE_TABLE_OFFSET).plus(index << LOG_BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY);
190    if (VM.VERIFY_ASSERTIONS) {
191      Address block = chunk.plus(index << LOG_BYTES_IN_BLOCK);
192      VM.assertions._assert(isAligned(block));
193      boolean valid = rtn.GE(chunk.plus(Chunk.BLOCK_DEFRAG_STATE_TABLE_OFFSET)) && rtn.LT(chunk.plus(Chunk.BLOCK_DEFRAG_STATE_TABLE_OFFSET + BLOCK_DEFRAG_STATE_TABLE_BYTES));
194      VM.assertions._assert(valid);
195    }
196    return rtn;
197  }
198
199  static void resetLineMarksAndDefragStateTable(short threshold, Address markStateBase, Address defragStateBase,
200      Address lineMarkBase, int block) {
201    Offset csOffset = Offset.fromIntZeroExtend(block << LOG_BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY);
202    short state = defragStateBase.loadShort(csOffset);
203    short defragState = BLOCK_IS_NOT_DEFRAG_SOURCE;
204    if (state >= threshold) defragState = BLOCK_IS_DEFRAG_SOURCE;
205    defragStateBase.store(defragState, csOffset);
206  }
207
208  private static final short UNALLOCATED_BLOCK_STATE = 0;
209  private static final short UNMARKED_BLOCK_STATE = (short) (MAX_BLOCK_MARK_STATE + 1);
210  private static final short REUSED_BLOCK_STATE = (short) (MAX_BLOCK_MARK_STATE + 2);
211
212  private static final short BLOCK_IS_NOT_DEFRAG_SOURCE = 0;
213  private static final short BLOCK_IS_DEFRAG_SOURCE = 1;
214
215  /* block states */
216  static final int LOG_BYTES_IN_BLOCK_STATE_ENTRY = LOG_BYTES_IN_SHORT; // use a short for now
217  static final int BYTES_IN_BLOCK_STATE_ENTRY = 1 << LOG_BYTES_IN_BLOCK_STATE_ENTRY;
218  static final int BLOCK_STATE_TABLE_BYTES = BLOCKS_IN_CHUNK << LOG_BYTES_IN_BLOCK_STATE_ENTRY;
219
220  /* per-block defrag state */
221  static final int LOG_BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY = LOG_BYTES_IN_SHORT;
222  static final int BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY = 1 << LOG_BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY;
223
224  static final int BLOCK_DEFRAG_STATE_TABLE_BYTES = BLOCKS_IN_CHUNK << LOG_BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY;
225}