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.jikesrvm.mm.mmtk;
014
015 import org.mmtk.plan.TraceLocal;
016 import org.mmtk.utility.Constants;
017 import org.mmtk.utility.Log;
018 import org.jikesrvm.VM;
019 import org.jikesrvm.runtime.BootRecord;
020 import org.jikesrvm.runtime.Magic;
021 import org.jikesrvm.scheduler.RVMThread;
022 import org.jikesrvm.mm.mminterface.CollectorThread;
023 import org.jikesrvm.mm.mminterface.MemoryManager;
024
025 import org.vmmagic.unboxed.*;
026 import org.vmmagic.pragma.*;
027
028 /**
029 * Scan the boot image for references using the boot image reference map
030 */
031 public class ScanBootImage implements Constants {
032
033 private static final boolean DEBUG = false;
034 private static final boolean FILTER = true;
035
036 private static final int LOG_CHUNK_BYTES = 12;
037 private static final int CHUNK_BYTES = 1<<LOG_CHUNK_BYTES;
038 private static final int LONGENCODING_MASK = 0x1;
039 private static final int RUN_MASK = 0x2;
040 private static final int MAX_RUN = (1<<BITS_IN_BYTE)-1;
041 private static final int LONGENCODING_OFFSET_BYTES = 4;
042 private static final int GUARD_REGION = LONGENCODING_OFFSET_BYTES + 1; /* long offset + run encoding */
043
044 /* statistics */
045 static int roots = 0;
046 static int refs = 0;
047
048 /****************************************************************************
049 *
050 * GC-time decoding (multi-threaded)
051 */
052
053 /**
054 * Scan the boot image for object references. Executed by
055 * all GC threads in parallel, with each doing a portion of the
056 * boot image.
057 *
058 * @param trace The trace object to which the roots should be added
059 */
060 @Inline
061 @Uninterruptible
062 public static void scanBootImage(TraceLocal trace) {
063 /* establish sentinals in map & image */
064 Address mapStart = BootRecord.the_boot_record.bootImageRMapStart;
065 Address mapEnd = BootRecord.the_boot_record.bootImageRMapEnd;
066 Address imageStart = BootRecord.the_boot_record.bootImageDataStart;
067
068 /* figure out striding */
069 int stride = CollectorThread.numCollectors()<<LOG_CHUNK_BYTES;
070 CollectorThread collector = Magic.threadAsCollectorThread(RVMThread.getCurrentThread());
071 int start = (collector.getGCOrdinal() - 1)<<LOG_CHUNK_BYTES;
072 Address cursor = mapStart.plus(start);
073
074 /* statistics */
075 roots = 0;
076 refs = 0;
077
078 /* process chunks in parallel till done */
079 while (cursor.LT(mapEnd)) {
080 processChunk(cursor, imageStart, mapStart, mapEnd, trace);
081 cursor = cursor.plus(stride);
082 }
083
084 /* print some debugging stats */
085 if (DEBUG) {
086 Log.write("<boot image");
087 Log.write(" roots: "); Log.write(roots);
088 Log.write(" refs: "); Log.write(refs);
089 Log.write(">");
090 }
091 }
092
093 /**
094 * Process a chunk of encoded reference data, enqueuing each
095 * reference (optionally filtering them on whether they point
096 * outside the boot image).
097 *
098 * @param chunkStart The address of the first byte of encoded data
099 * @param imageStart The address of the start of the boot image
100 * @param mapStart The address of the start of the encoded reference map
101 * @param mapEnd The address of the end of the encoded reference map
102 * @param trace The <code>TraceLocal</code> into which roots should
103 * be enqueued.
104 */
105 @Inline
106 @Uninterruptible
107 private static void processChunk(Address chunkStart, Address imageStart,
108 Address mapStart, Address mapEnd, TraceLocal trace) {
109 int value;
110 Offset offset = Offset.zero();
111 Address cursor = chunkStart;
112 while ((value = (cursor.loadByte() & 0xff)) != 0) {
113 /* establish the offset */
114 if ((value & LONGENCODING_MASK) != 0) {
115 offset = decodeLongEncoding(cursor);
116 cursor = cursor.plus(LONGENCODING_OFFSET_BYTES);
117 } else {
118 offset = offset.plus(value & 0xfc);
119 cursor = cursor.plus(1);
120 }
121 /* figure out the length of the run, if any */
122 int runlength = 0;
123 if ((value & RUN_MASK) != 0) {
124 runlength = cursor.loadByte() & 0xff;
125 cursor = cursor.plus(1);
126 }
127 /* enqueue the specified slot or slots */
128 if (VM.VerifyAssertions) VM._assert(isAddressAligned(offset));
129 Address slot = imageStart.plus(offset);
130 if (DEBUG) refs++;
131 if (!FILTER || slot.loadAddress().GT(mapEnd)) {
132 if (DEBUG) roots++;
133 trace.processRootEdge(slot, false);
134 }
135 if (runlength != 0) {
136 for (int i = 0; i < runlength; i++) {
137 offset = offset.plus(BYTES_IN_ADDRESS);
138 slot = imageStart.plus(offset);
139 if (VM.VerifyAssertions) VM._assert(isAddressAligned(slot));
140 if (DEBUG) refs++;
141 if (!FILTER || slot.loadAddress().GT(mapEnd)) {
142 if (DEBUG) roots++;
143 if (ScanThread.VALIDATE_REFS) checkReference(slot);
144 trace.processRootEdge(slot, false);
145 }
146 }
147 }
148 }
149 }
150
151 /**
152 * Check that a reference encountered during scanning is valid. If
153 * the reference is invalid, dump stack and die.
154 *
155 * @param refaddr The address of the reference in question.
156 */
157 @Uninterruptible
158 private static void checkReference(Address refaddr) {
159 ObjectReference ref = org.mmtk.vm.VM.activePlan.global().loadObjectReference(refaddr);
160 if (!MemoryManager.validRef(ref)) {
161 Log.writeln();
162 Log.writeln("Invalid ref reported while scanning boot image");
163 Log.writeln();
164 Log.write(refaddr); Log.write(":"); Log.flush(); MemoryManager.dumpRef(ref);
165 Log.writeln();
166 Log.writeln("Dumping stack:");
167 RVMThread.dumpStack();
168 VM.sysFail("\n\nScanStack: Detected bad GC map; exiting RVM with fatal error");
169 }
170 }
171
172 /**
173 * Return true if the given offset is address-aligned
174 * @param offset the offset to be check
175 * @return true if the offset is address aligned.
176 */
177 @Uninterruptible
178 private static boolean isAddressAligned(Offset offset) {
179 return (offset.toLong()>>LOG_BYTES_IN_ADDRESS)<<LOG_BYTES_IN_ADDRESS == offset.toLong();
180 }
181
182 /**
183 * Return true if the given address is address-aligned
184 * @param address the address to be check
185 * @return true if the address is address aligned.
186 */
187 @Uninterruptible
188 private static boolean isAddressAligned(Address address) {
189 return (address.toLong()>>LOG_BYTES_IN_ADDRESS)<<LOG_BYTES_IN_ADDRESS == address.toLong();
190 }
191
192 /****************************************************************************
193 *
194 * Build-time encoding (assumed to be single-threaded)
195 */
196 private static int lastOffset = Integer.MIN_VALUE / 2; /* bootstrap value */
197 private static int oldIndex = 0;
198 private static int codeIndex = 0;
199
200 /* statistics */
201 private static int shortRefs = 0;
202 private static int runRefs = 0;
203 private static int longRefs = 0;
204 private static int startRefs = 0;
205
206 /**
207 * Take a bytemap encoding of all references in the boot image, and
208 * produce an encoded byte array. Return the total length of the
209 * encoding.
210 */
211 public static int encodeRMap(byte[] bootImageRMap, byte[] referenceMap,
212 int referenceMapLimit) {
213 for (int index = 0; index <= referenceMapLimit; index++) {
214 if (referenceMap[index] == 1) {
215 addOffset(bootImageRMap, index<<LOG_BYTES_IN_ADDRESS);
216 }
217 }
218 return codeIndex + 1;
219 }
220
221 /**
222 * Print some basic statistics about the encoded references, for
223 * debugging purposes.
224 */
225 public static void encodingStats() {
226 if (DEBUG) {
227 Log.write("refs: "); Log.writeln(startRefs + shortRefs + longRefs + runRefs);
228 Log.write("start: "); Log.writeln(startRefs);
229 Log.write("short: "); Log.writeln(shortRefs);
230 Log.write("long: "); Log.writeln(longRefs);
231 Log.write("run: "); Log.writeln(runRefs);
232 Log.write("size: "); Log.writeln(codeIndex);
233 }
234 }
235
236 /**
237 * Encode a given offset (distance from the start of the boot image)
238 * into the code array.
239 *
240 * @param code A byte array into which the value should be encoded
241 * @param offset The offset value to be encoded
242 */
243 private static void addOffset(byte[] code, int offset) {
244 if ((codeIndex ^ (codeIndex + GUARD_REGION)) >= CHUNK_BYTES) {
245 codeIndex = (codeIndex + GUARD_REGION) & ~(CHUNK_BYTES - 1);
246 oldIndex = codeIndex;
247 codeIndex = encodeLongEncoding(code, codeIndex, offset);
248 if (DEBUG) {
249 startRefs++;
250 Log.write("[chunk: "); Log.write(codeIndex);
251 Log.write(" offset: "); Log.write(offset);
252 Log.write(" last offset: "); Log.write(lastOffset);
253 Log.writeln("]");
254 }
255 } else {
256 int delta = offset - lastOffset;
257 if (VM.VerifyAssertions) VM._assert((delta & 0x3) == 0);
258 if (VM.VerifyAssertions) VM._assert(delta > 0);
259
260 int currentrun = ((int) code[codeIndex]) & 0xff;
261 if ((delta == BYTES_IN_ADDRESS) &&
262 (currentrun < MAX_RUN)) {
263 currentrun++;
264 code[codeIndex] = (byte) (currentrun & 0xff);
265 code[oldIndex] |= RUN_MASK;
266 if (DEBUG) runRefs++;
267 } else {
268 if (currentrun != 0) codeIndex++;
269 oldIndex = codeIndex;
270 if (delta < 1<<BITS_IN_BYTE) {
271 /* common case: single byte encoding */
272 code[codeIndex++] = (byte) (delta & 0xff);
273 if (DEBUG) shortRefs++;
274 } else {
275 /* else four byte encoding */
276 codeIndex = encodeLongEncoding(code, codeIndex, offset);
277 if (DEBUG) longRefs++;
278 }
279 }
280 }
281 if (offset != getOffset(code, oldIndex, lastOffset)) {
282 Log.write("offset: "); Log.writeln(offset);
283 Log.write("last offset: "); Log.writeln(lastOffset);
284 Log.write("offset: "); Log.writeln(getOffset(code, oldIndex, lastOffset));
285 Log.write("index: "); Log.writeln(oldIndex);
286 Log.write("index: "); Log.writeln(oldIndex & (CHUNK_BYTES - 1));
287 Log.writeln();
288 Log.write("1: "); Log.writeln(code[oldIndex]);
289 Log.write("2: "); Log.writeln(code[oldIndex+1]);
290 Log.write("3: "); Log.writeln(code[oldIndex+2]);
291 Log.write("4: "); Log.writeln(code[oldIndex+3]);
292 Log.write("5: "); Log.writeln(code[oldIndex+4]);
293 if (VM.VerifyAssertions)
294 VM._assert(offset == getOffset(code, oldIndex, lastOffset));
295 }
296 lastOffset = offset;
297 }
298
299 /****************************************************************************
300 *
301 * Utility encoding and decoding methods
302 */
303
304 /**
305 * Decode an encoded offset given the coded byte array, and index
306 * into it, and the current (last) offset.
307 *
308 * @param code A byte array containing the encoded value
309 * @param index The offset into the code array from which to
310 * commence decoding
311 * @param lastOffset The current (last) encoded offset
312 * @return The next offset, which is either explicitly encoded in
313 * the byte array or inferred from an encoded delta and the last
314 * offset.
315 */
316 private static int getOffset(byte[] code, int index, int lastOffset) {
317 if (((int) code[index] & RUN_MASK) == RUN_MASK) {
318 return lastOffset + BYTES_IN_WORD;
319 } else {
320 if (((index & (CHUNK_BYTES - 1)) == 0) ||
321 (((int) code[index] &LONGENCODING_MASK) == LONGENCODING_MASK)) {
322 return decodeLongEncoding(code, index);
323 } else {
324 return lastOffset + (((int) code[index]) & 0xff);
325 }
326 }
327 }
328
329 /**
330 * Decode a 4-byte encoding, taking a pointer to the first byte of
331 * the encoding, and returning the encoded value as an <code>Offset</code>
332 *
333 * @param cursor A pointer to the first byte of encoded data
334 * @return The encoded value as an <code>Offset</code>
335 */
336 @Inline
337 @Uninterruptible
338 private static Offset decodeLongEncoding(Address cursor) {
339 int value;
340 value = ((int) cursor.loadByte()) & 0x000000fc;
341 value |= ((int) cursor.loadByte(Offset.fromIntSignExtend(1))<<BITS_IN_BYTE) & 0x0000ff00;
342 value |= ((int) cursor.loadByte(Offset.fromIntSignExtend(2))<<(2*BITS_IN_BYTE)) & 0x00ff0000;
343 value |= ((int) cursor.loadByte(Offset.fromIntSignExtend(3))<<(3*BITS_IN_BYTE)) & 0xff000000;
344 return Offset.fromIntSignExtend(value);
345 }
346
347 /**
348 * Decode a 4-byte encoding, taking a byte array and an index into
349 * it and returning the encoded value as an integer
350 *
351 * @param code A byte array containing the encoded value
352 * @param index The offset into the code array from which to
353 * commence decoding
354 * @return The encoded value as an integer
355 */
356 @Inline
357 @Uninterruptible
358 private static int decodeLongEncoding(byte[] code, int index) {
359 int value;
360 value = ((int) code[index]) & 0x000000fc;
361 value |= ((int) code[index+1]<<BITS_IN_BYTE) & 0x0000ff00;
362 value |= ((int) code[index+2]<<(2*BITS_IN_BYTE)) & 0x00ff0000;
363 value |= ((int) code[index+3]<<(3*BITS_IN_BYTE)) & 0xff000000;
364 return value;
365 }
366
367 /**
368 * Encode a 4-byte encoding, taking a byte array, the current index into
369 * it, and the value to be encoded.
370 *
371 * @param code A byte array to containthe encoded value
372 * @param index The current offset into the code array
373 * @param value The value to be encoded
374 * @return The updated index into the code array
375 */
376 private static int encodeLongEncoding(byte[] code, int index, int value) {
377 code[index++] = (byte) ((value & 0xff) | LONGENCODING_MASK);
378 value = value >>> BITS_IN_BYTE;
379 code[index++] = (byte) (value & 0xff);
380 value = value >>> BITS_IN_BYTE;
381 code[index++] = (byte) (value & 0xff);
382 value = value >>> BITS_IN_BYTE;
383 code[index++] = (byte) (value & 0xff);
384 return index;
385 }
386
387 }