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.mmtk.policy.immix;
014
015import static org.mmtk.policy.immix.ImmixConstants.*;
016
017import org.mmtk.vm.VM;
018
019import org.vmmagic.pragma.Inline;
020import org.vmmagic.pragma.Uninterruptible;
021import org.vmmagic.unboxed.Address;
022import org.vmmagic.unboxed.ObjectReference;
023import org.vmmagic.unboxed.Offset;
024
025@Uninterruptible
026public class Line {
027
028  public static Address align(Address ptr) {
029    return ptr.toWord().and(LINE_MASK.not()).toAddress();
030  }
031
032  public static boolean isAligned(Address address) {
033    return address.EQ(align(address));
034  }
035
036  static int getChunkIndex(Address line) {
037    return line.toWord().and(CHUNK_MASK).rshl(LOG_BYTES_IN_LINE).toInt();
038  }
039
040 /***************************************************************************
041  * Line marking
042  */
043
044  /**
045   * Marks a line.
046   *
047   * @param address the line's address
048   * @param markValue the value to use for marking
049   */
050  static void mark(Address address, final byte markValue) {
051    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!Block.isUnused(Block.align(address)));
052    getMarkAddress(address).store(markValue);
053  }
054
055  static void markMultiLine(Address start, ObjectReference object, final byte markValue) {
056    /* endLine is the address of the last (highest) line touched by this object */
057    Address endLine = Line.align(VM.objectModel.getObjectEndAddress(object).minus(1));
058    Address line = Line.align(start.plus(BYTES_IN_LINE));
059    while (line.LT(endLine)) {
060      if (VM.VERIFY_ASSERTIONS)
061        VM.assertions._assert(Block.align(start).EQ(Block.align(line)));
062      mark(line, markValue);
063      line = line.plus(BYTES_IN_LINE);
064    }
065  }
066
067  /***************************************************************************
068   * Scanning through avail lines
069   */
070
071  /**
072   * @param chunk the chunk's address
073   * @return the address of the chunk mark table
074   */
075  public static Address getChunkMarkTable(Address chunk) {
076    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(Chunk.isAligned(chunk));
077    return getMarkAddress(chunk);
078  }
079
080  public static Address getBlockMarkTable(Address block) {
081    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(Block.isAligned(block));
082    return getMarkAddress(block);
083  }
084
085  @Inline
086  public static int getNextUnavailable(Address baseLineAvailAddress, int line, final byte unavailableState) {
087    while (line < LINES_IN_BLOCK &&
088        baseLineAvailAddress.loadByte(Offset.fromIntZeroExtend(line << Line.LOG_BYTES_IN_LINE_STATUS)) < unavailableState)
089      line++;
090    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(line >= 0 && line <= LINES_IN_BLOCK);
091    return line;
092  }
093
094  @Inline
095  public static int getNextAvailable(Address baseLineAvailAddress, int line, final byte unavailableState) {
096    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(line >= 0 && line < LINES_IN_BLOCK);
097    byte last = baseLineAvailAddress.loadByte(Offset.fromIntZeroExtend(line << Line.LOG_BYTES_IN_LINE_STATUS));
098    byte thisline;
099    line++;
100    while (line < LINES_IN_BLOCK) {
101      thisline = baseLineAvailAddress.loadByte(Offset.fromIntZeroExtend(line << Line.LOG_BYTES_IN_LINE_STATUS));
102      if (thisline < unavailableState && last < unavailableState)
103        break;
104      last = thisline;
105      line++;
106    }
107    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(line >= 0 && line <= LINES_IN_BLOCK);
108    return line;
109  }
110
111  private static Address getMetaAddress(Address address, final int tableOffset) {
112    Address chunk = Chunk.align(address);
113    int index = getChunkIndex(address);
114    Address rtn = chunk.plus(tableOffset + (index << LOG_BYTES_IN_LINE_STATUS));
115    if (VM.VERIFY_ASSERTIONS) {
116      Address line = chunk.plus(index << LOG_BYTES_IN_LINE);
117      VM.assertions._assert(isAligned(line));
118      VM.assertions._assert(align(address).EQ(line));
119      boolean valid = rtn.GE(chunk.plus(tableOffset)) && rtn.LT(chunk.plus(tableOffset + LINE_MARK_TABLE_BYTES));
120      VM.assertions._assert(valid);
121    }
122    return rtn;
123  }
124
125  private static Address getMarkAddress(Address address) {
126    return getMetaAddress(address, Chunk.LINE_MARK_TABLE_OFFSET);
127  }
128
129  /* per-line mark bytes */
130
131  static final int LOG_BYTES_IN_LINE_STATUS = 0;
132  static final int BYTES_IN_LINE_STATUS = 1 << LOG_BYTES_IN_LINE_STATUS;
133
134  static final int LINE_MARK_TABLE_BYTES = LINES_IN_CHUNK << LOG_BYTES_IN_LINE_STATUS;
135  static final int LOG_LINE_MARK_BYTES_PER_BLOCK = LOG_LINES_IN_BLOCK + LOG_BYTES_IN_LINE_STATUS;
136  static final int LINE_MARK_BYTES_PER_BLOCK = (1 << LOG_LINE_MARK_BYTES_PER_BLOCK);
137}