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.jikesrvm.mm.mmtk;
014
015import static org.mmtk.utility.Constants.*;
016
017import org.mmtk.plan.CollectorContext;
018import org.mmtk.plan.TraceLocal;
019import org.mmtk.utility.Log;
020import org.jikesrvm.VM;
021import org.jikesrvm.runtime.BootRecord;
022import org.jikesrvm.scheduler.RVMThread;
023import org.jikesrvm.mm.mminterface.MemoryManager;
024
025import org.vmmagic.unboxed.*;
026import org.vmmagic.pragma.*;
027
028/**
029 * Scan the boot image for references using the boot image reference map
030 */
031public class ScanBootImage {
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    CollectorContext collector = RVMThread.getCurrentThread().getCollectorContext();
070    int stride = collector.parallelWorkerCount() << LOG_CHUNK_BYTES;
071    int start = collector.parallelWorkerOrdinal() << 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
197  /** */
198  private static int lastOffset = Integer.MIN_VALUE / 2;  /* bootstrap value */
199  private static int oldIndex = 0;
200  private static int codeIndex = 0;
201
202  /* statistics */
203  private static int shortRefs = 0;
204  private static int runRefs = 0;
205  private static int longRefs = 0;
206  private static int startRefs = 0;
207
208  /**
209   * Take a bytemap encoding of all references in the boot image, and
210   * produce an encoded byte array.  Return the total length of the
211   * encoding.
212   *
213   * @param bootImageRMap space for the compressed reference map. The map
214   *  is initially empty and will be filled during execution of this method.
215   * @param referenceMap the (uncompressed) reference map for the bootimage
216   * @param referenceMapLimit the highest index in the referenceMap that
217   *  contains a reference
218   * @return the total length of the encoding
219   */
220  public static int encodeRMap(byte[] bootImageRMap, byte[] referenceMap,
221      int referenceMapLimit) {
222    for (int index = 0; index <= referenceMapLimit; index++) {
223      if (referenceMap[index] == 1) {
224        addOffset(bootImageRMap, index << LOG_BYTES_IN_ADDRESS);
225      }
226    }
227    return codeIndex + 1;
228  }
229
230  /**
231   * Print some basic statistics about the encoded references, for
232   * debugging purposes.
233   */
234  public static void encodingStats() {
235    if (DEBUG) {
236      Log.write("refs: "); Log.writeln(startRefs + shortRefs + longRefs + runRefs);
237      Log.write("start: "); Log.writeln(startRefs);
238      Log.write("short: "); Log.writeln(shortRefs);
239      Log.write("long: "); Log.writeln(longRefs);
240      Log.write("run: "); Log.writeln(runRefs);
241      Log.write("size: "); Log.writeln(codeIndex);
242    }
243  }
244
245  /**
246   * Encode a given offset (distance from the start of the boot image)
247   * into the code array.
248   *
249   * @param code A byte array into which the value should be encoded
250   * @param offset The offset value to be encoded
251   */
252  private static void addOffset(byte[] code, int offset) {
253    if ((codeIndex ^ (codeIndex + GUARD_REGION)) >= CHUNK_BYTES) {
254      codeIndex = (codeIndex + GUARD_REGION) & ~(CHUNK_BYTES - 1);
255      oldIndex = codeIndex;
256      codeIndex = encodeLongEncoding(code, codeIndex, offset);
257      if (DEBUG) {
258        startRefs++;
259        Log.write("[chunk: "); Log.write(codeIndex);
260        Log.write(" offset: "); Log.write(offset);
261        Log.write(" last offset: "); Log.write(lastOffset);
262        Log.writeln("]");
263      }
264    } else {
265      int delta = offset - lastOffset;
266      if (VM.VerifyAssertions) VM._assert((delta & 0x3) == 0);
267      if (VM.VerifyAssertions) VM._assert(delta > 0);
268
269      int currentrun = (code[codeIndex]) & 0xff;
270      if ((delta == BYTES_IN_ADDRESS) &&
271          (currentrun < MAX_RUN)) {
272        currentrun++;
273        code[codeIndex] = (byte) (currentrun & 0xff);
274        code[oldIndex] |= RUN_MASK;
275        if (DEBUG) runRefs++;
276      } else {
277        if (currentrun != 0) codeIndex++;
278        oldIndex = codeIndex;
279        if (delta < 1 << BITS_IN_BYTE) {
280          /* common case: single byte encoding */
281          code[codeIndex++] = (byte) (delta & 0xff);
282          if (DEBUG) shortRefs++;
283        } else {
284          /* else four byte encoding */
285          codeIndex = encodeLongEncoding(code, codeIndex, offset);
286          if (DEBUG) longRefs++;
287        }
288      }
289    }
290    if (offset != getOffset(code, oldIndex, lastOffset)) {
291      Log.write("offset: "); Log.writeln(offset);
292      Log.write("last offset: "); Log.writeln(lastOffset);
293      Log.write("offset: "); Log.writeln(getOffset(code, oldIndex, lastOffset));
294      Log.write("index: "); Log.writeln(oldIndex);
295      Log.write("index: "); Log.writeln(oldIndex & (CHUNK_BYTES - 1));
296      Log.writeln();
297      Log.write("1: "); Log.writeln(code[oldIndex]);
298      Log.write("2: "); Log.writeln(code[oldIndex + 1]);
299      Log.write("3: "); Log.writeln(code[oldIndex + 2]);
300      Log.write("4: "); Log.writeln(code[oldIndex + 3]);
301      Log.write("5: "); Log.writeln(code[oldIndex + 4]);
302      if (VM.VerifyAssertions)
303        VM._assert(offset == getOffset(code, oldIndex, lastOffset));
304    }
305    lastOffset = offset;
306  }
307
308  /****************************************************************************
309   *
310   * Utility encoding and decoding methods
311   */
312
313  /**
314   * Decode an encoded offset given the coded byte array, and index
315   * into it, and the current (last) offset.
316   *
317   * @param code A byte array containing the encoded value
318   * @param index The offset into the code array from which to
319   * commence decoding
320   * @param lastOffset The current (last) encoded offset
321   * @return The next offset, which is either explicitly encoded in
322   * the byte array or inferred from an encoded delta and the last
323   * offset.
324 */
325  private static int getOffset(byte[] code, int index, int lastOffset) {
326    if ((code[index] & RUN_MASK) == RUN_MASK) {
327      return lastOffset + BYTES_IN_WORD;
328    } else {
329      if (((index & (CHUNK_BYTES - 1)) == 0) ||
330          ((code[index] & LONGENCODING_MASK) == LONGENCODING_MASK)) {
331        return decodeLongEncoding(code, index);
332      } else {
333        return lastOffset + ((code[index]) & 0xff);
334      }
335    }
336  }
337
338  /**
339   * Decode a 4-byte encoding, taking a pointer to the first byte of
340   * the encoding, and returning the encoded value as an <code>Offset</code>
341   *
342   * @param cursor A pointer to the first byte of encoded data
343   * @return The encoded value as an <code>Offset</code>
344   */
345  @Inline
346  @Uninterruptible
347  private static Offset decodeLongEncoding(Address cursor) {
348    int value;
349    value  = (cursor.loadByte())                                              & 0x000000fc;
350    value |= (cursor.loadByte(Offset.fromIntSignExtend(1)) << BITS_IN_BYTE)     & 0x0000ff00;
351    value |= (cursor.loadByte(Offset.fromIntSignExtend(2)) << (2 * BITS_IN_BYTE)) & 0x00ff0000;
352    value |= (cursor.loadByte(Offset.fromIntSignExtend(3)) << (3 * BITS_IN_BYTE)) & 0xff000000;
353    return Offset.fromIntSignExtend(value);
354  }
355
356  /**
357   * Decode a 4-byte encoding, taking a byte array and an index into
358   * it and returning the encoded value as an integer
359   *
360   * @param code A byte array containing the encoded value
361   * @param index The offset into the code array from which to
362   * commence decoding
363   * @return The encoded value as an integer
364   */
365  @Inline
366  @Uninterruptible
367  private static int decodeLongEncoding(byte[] code, int index) {
368    int value;
369    value  = (code[index])                     & 0x000000fc;
370    value |= (code[index + 1] << BITS_IN_BYTE)     & 0x0000ff00;
371    value |= (code[index + 2] << (2 * BITS_IN_BYTE)) & 0x00ff0000;
372    value |= (code[index + 3] << (3 * BITS_IN_BYTE)) & 0xff000000;
373    return value;
374  }
375
376  /**
377   * Encode a 4-byte encoding, taking a byte array, the current index into
378   * it, and the value to be encoded.
379   *
380   * @param code A byte array to contain the encoded value
381   * @param index The current offset into the code array
382   * @param value The value to be encoded
383   * @return The updated index into the code array
384   */
385  private static int encodeLongEncoding(byte[] code, int index, int value) {
386    code[index++] = (byte) ((value & 0xff) | LONGENCODING_MASK);
387    value = value >>> BITS_IN_BYTE;
388    code[index++] = (byte) (value & 0xff);
389    value = value >>> BITS_IN_BYTE;
390    code[index++] = (byte) (value & 0xff);
391    value = value >>> BITS_IN_BYTE;
392    code[index++] = (byte) (value & 0xff);
393    return index;
394  }
395
396}