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