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