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 public static boolean isUnused(final Address address) {
048 return getBlockMarkState(address) == UNALLOCATED_BLOCK_STATE;
049 }
050
051 static boolean isUnusedState(Address cursor) {
052 return cursor.loadShort() == UNALLOCATED_BLOCK_STATE;
053 }
054
055 static short getMarkState(Address cursor) {
056 return cursor.loadShort();
057 }
058
059 static void setState(Address cursor, short value) {
060 cursor.store(value);
061 }
062
063 public static short getBlockMarkState(Address address) {
064 return getBlockMarkStateAddress(address).loadShort();
065 }
066
067 static void setBlockAsInUse(Address address) {
068 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isUnused(address));
069 setBlockState(address, UNMARKED_BLOCK_STATE);
070 }
071
072 public static void setBlockAsReused(Address address) {
073 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!isUnused(address));
074 setBlockState(address, REUSED_BLOCK_STATE);
075 }
076
077 static void setBlockAsUnallocated(Address address) {
078 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!isUnused(address));
079 getBlockMarkStateAddress(address).store(UNALLOCATED_BLOCK_STATE);
080 }
081
082 private static void setBlockState(Address address, short value) {
083 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(value != UNALLOCATED_BLOCK_STATE);
084 getBlockMarkStateAddress(address).store(value);
085 }
086
087 static Address getBlockMarkStateAddress(Address address) {
088 Address chunk = Chunk.align(address);
089 int index = getChunkIndex(address);
090 Address rtn = chunk.plus(Chunk.BLOCK_STATE_TABLE_OFFSET).plus(index<<LOG_BYTES_IN_BLOCK_STATE_ENTRY);
091 if (VM.VERIFY_ASSERTIONS) {
092 Address block = chunk.plus(index<<LOG_BYTES_IN_BLOCK);
093 VM.assertions._assert(isAligned(block));
094 boolean valid = rtn.GE(chunk.plus(Chunk.BLOCK_STATE_TABLE_OFFSET)) && rtn.LT(chunk.plus(Chunk.BLOCK_STATE_TABLE_OFFSET+BLOCK_STATE_TABLE_BYTES));
095 VM.assertions._assert(valid);
096 }
097 return rtn;
098 }
099
100 /***************************************************************************
101 * Sweeping
102 */
103 static short sweepOneBlock(Address block, int[] markHistogram, final byte markState, final boolean resetMarkState) {
104 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isAligned(block));
105
106 final boolean unused = isUnused(block);
107 if (unused && !SANITY_CHECK_LINE_MARKS)
108 return 0;
109
110 Address markTable = Line.getBlockMarkTable(block);
111
112 short markCount = 0;
113 short conservativeSpillCount = 0;
114 byte mark, lastMark = 0;
115 for (int offset = 0; offset < (LINES_IN_BLOCK<<Line.LOG_BYTES_IN_LINE_STATUS); offset += Line.BYTES_IN_LINE_STATUS) {
116 if (VM.VERIFY_ASSERTIONS) {
117 VM.assertions._assert(markTable.plus(offset).GE(Chunk.align(block).plus(Chunk.LINE_MARK_TABLE_OFFSET)));
118 VM.assertions._assert(markTable.plus(offset).LT(Chunk.align(block).plus(Chunk.LINE_MARK_TABLE_OFFSET+Line.LINE_MARK_TABLE_BYTES)));
119 }
120 mark = markTable.loadByte(Offset.fromIntZeroExtend(offset));
121 if (resetMarkState)
122 markTable.store((byte) (mark == markState ? RESET_LINE_MARK_STATE : 0), Offset.fromIntZeroExtend(offset));
123
124 if (mark == markState)
125 markCount++;
126 else if (lastMark == markState)
127 conservativeSpillCount++;
128 else if (SANITY_CHECK_LINE_MARKS && lastMark != markState) {
129 VM.memory.zero(block.plus(offset<<(LOG_BYTES_IN_LINE-Line.LOG_BYTES_IN_LINE_STATUS)),Extent.fromIntZeroExtend(BYTES_IN_LINE));
130 }
131
132 lastMark = mark;
133 }
134 if (VM.VERIFY_ASSERTIONS) {
135 VM.assertions._assert(markCount <= LINES_IN_BLOCK);
136 VM.assertions._assert(markCount + conservativeSpillCount <= LINES_IN_BLOCK);
137 VM.assertions._assert(markCount == 0 || !isUnused(block));
138 }
139
140 getDefragStateAddress(block).store(conservativeSpillCount);
141 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(markCount >= conservativeSpillCount);
142 markHistogram[conservativeSpillCount] += markCount;
143
144 markCount = (short) (markCount + conservativeSpillCount);
145
146 return markCount;
147 }
148
149 /****************************************************************************
150 * Block defrag state
151 */
152 public static boolean isDefragSource(Address address) {
153 return getDefragStateAddress(address).loadShort() == BLOCK_IS_DEFRAG_SOURCE;
154 }
155
156 static void clearConservativeSpillCount(Address address) {
157 getDefragStateAddress(address).store((short) 0);
158 }
159
160 static short getConservativeSpillCount(Address address) {
161 return getDefragStateAddress(address).loadShort();
162 }
163
164 static Address getDefragStateAddress(Address address) {
165 Address chunk = Chunk.align(address);
166 int index = getChunkIndex(address);
167 Address rtn = chunk.plus(Chunk.BLOCK_DEFRAG_STATE_TABLE_OFFSET).plus(index<<LOG_BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY);
168 if (VM.VERIFY_ASSERTIONS) {
169 Address block = chunk.plus(index<<LOG_BYTES_IN_BLOCK);
170 VM.assertions._assert(isAligned(block));
171 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));
172 VM.assertions._assert(valid);
173 }
174 return rtn;
175 }
176
177 static void resetLineMarksAndDefragStateTable(short threshold, Address markStateBase, Address defragStateBase,
178 Address lineMarkBase, int block) {
179 Offset csOffset = Offset.fromIntZeroExtend(block<<LOG_BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY);
180 short state = defragStateBase.loadShort(csOffset);
181 short defragState = BLOCK_IS_NOT_DEFRAG_SOURCE;
182 if (state >= threshold) defragState = BLOCK_IS_DEFRAG_SOURCE;
183 defragStateBase.store(defragState, csOffset);
184 }
185
186 private static final short UNALLOCATED_BLOCK_STATE = 0;
187 private static final short UNMARKED_BLOCK_STATE = (short) (MAX_BLOCK_MARK_STATE + 1);
188 private static final short REUSED_BLOCK_STATE = (short) (MAX_BLOCK_MARK_STATE + 2);
189
190 private static final short BLOCK_IS_NOT_DEFRAG_SOURCE = 0;
191 private static final short BLOCK_IS_DEFRAG_SOURCE = 1;
192
193 /* block states */
194 static final int LOG_BYTES_IN_BLOCK_STATE_ENTRY = LOG_BYTES_IN_SHORT; // use a short for now
195 static final int BYTES_IN_BLOCK_STATE_ENTRY = 1<<LOG_BYTES_IN_BLOCK_STATE_ENTRY;
196 static final int BLOCK_STATE_TABLE_BYTES = BLOCKS_IN_CHUNK<<LOG_BYTES_IN_BLOCK_STATE_ENTRY;
197
198 /* per-block defrag state */
199 static final int LOG_BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY = LOG_BYTES_IN_SHORT;
200 static final int BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY = 1<<LOG_BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY;
201
202 static final int BLOCK_DEFRAG_STATE_TABLE_BYTES = BLOCKS_IN_CHUNK<<LOG_BYTES_IN_BLOCK_DEFRAG_STATE_ENTRY;
203 }