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
014package org.mmtk.policy.immix;
015
016import static org.mmtk.policy.immix.ImmixConstants.*;
017import static org.mmtk.utility.Constants.*;
018
019import org.mmtk.utility.Log;
020import org.mmtk.utility.heap.FreeListPageResource;
021import org.mmtk.utility.options.DefragFreeHeadroom;
022import org.mmtk.utility.options.DefragFreeHeadroomFraction;
023import org.mmtk.utility.options.DefragHeadroom;
024import org.mmtk.utility.options.DefragHeadroomFraction;
025import org.mmtk.utility.options.DefragLineReuseRatio;
026import org.mmtk.utility.options.DefragSimpleSpillThreshold;
027import org.mmtk.utility.options.DefragStress;
028import org.mmtk.utility.options.Options;
029import org.mmtk.utility.statistics.EventCounter;
030import org.mmtk.utility.statistics.SizeCounter;
031import org.mmtk.vm.VM;
032import org.vmmagic.pragma.Interruptible;
033import org.vmmagic.pragma.Uninterruptible;
034
035@Uninterruptible
036public class Defrag {
037  private boolean inDefragCollection = false;
038  private int debugBytesDefraged = 0;
039  private int availableCleanPagesForDefrag;
040  private boolean defragSpaceExhausted = true;
041  private int[][] spillMarkHistograms;
042  private final int[] spillAvailHistogram = new int[SPILL_HISTOGRAM_BUCKETS];
043  public static SizeCounter defragCleanBytesUsed = new SizeCounter("cleanUsed");
044
045  /* verbose stats (used only on stats runs since they induce overhead when gathered) */
046  public static SizeCounter defragBytesNotFreed = new SizeCounter("bytesNotFreed");
047  public static SizeCounter defragBytesFreed = new SizeCounter("bytesFreed");
048  public static SizeCounter defragCleanBytesAvailable = new SizeCounter("cleanAvail");
049
050  private final FreeListPageResource pr;
051  private boolean debugCollectionTypeDetermined = false;
052  static short defragSpillThreshold = 0;
053  static short defragReusableMarkStateThreshold = 0;
054  public static EventCounter defrags = new EventCounter("defrags");
055
056  static {
057    Options.defragLineReuseRatio = new DefragLineReuseRatio();
058    Options.defragHeadroom = new DefragHeadroom();
059    Options.defragHeadroomFraction = new DefragHeadroomFraction();
060    Options.defragFreeHeadroom = new DefragFreeHeadroom();
061    Options.defragFreeHeadroomFraction = new DefragFreeHeadroomFraction();
062    Options.defragSimpleSpillThreshold = new DefragSimpleSpillThreshold();
063    Options.defragStress = new DefragStress();
064    defragReusableMarkStateThreshold = (short) (Options.defragLineReuseRatio.getValue() * MAX_BLOCK_MARK_STATE);
065  }
066
067  Defrag(FreeListPageResource pr) {
068    this.pr = pr;
069  }
070
071  /**
072   * Prepares the histograms.<p>
073   *
074   * This needs to happen at runtime because the collector count is not known
075   * at build time.
076   */
077  @Interruptible
078  void prepareHistograms() {
079    int collectorCount = VM.activePlan.collectorCount();
080    spillMarkHistograms = new int[collectorCount][SPILL_HISTOGRAM_BUCKETS];
081  }
082
083  boolean inDefrag() {
084    return inDefragCollection;
085  }
086
087  void prepare(ChunkList chunkMap, ImmixSpace space) {
088    availableCleanPagesForDefrag = VM.activePlan.global().getTotalPages() - VM.activePlan.global().getPagesReserved() + getDefragHeadroomPages();
089    if (availableCleanPagesForDefrag < 0) availableCleanPagesForDefrag = 0;
090    defragSpaceExhausted = false;
091
092    /* Free defrag pages (not budgeted, used for experimentation) */
093    if (Options.defragFreeHeadroom.getPages() > 0) {
094      availableCleanPagesForDefrag += Options.defragFreeHeadroom.getPages();
095    } else if (Options.defragFreeHeadroomFraction.getValue() > 0) {
096      availableCleanPagesForDefrag += (int) (pr.reservedPages() * Options.defragFreeHeadroomFraction.getValue());
097    }
098
099    if (inDefragCollection) {
100      if (Options.verbose.getValue() > 0) {
101        Log.write("[Defrag]");
102      }
103      chunkMap.consolidateMap();
104      establishDefragSpillThreshold(chunkMap, space);
105      defrags.inc();
106      defragCleanBytesAvailable.inc(availableCleanPagesForDefrag << LOG_BYTES_IN_PAGE);
107    }
108    availableCleanPagesForDefrag += VM.activePlan.global().getCollectionReserve();
109  }
110
111  void globalRelease() {
112    if (inDefragCollection && Options.verbose.getValue() > 2) {
113      Log.write("(Defrag summary: cu: "); defragCleanBytesUsed.printCurrentVolume();
114      Log.write(" nf: "); defragBytesNotFreed.printCurrentVolume();
115      Log.write(" fr: "); defragBytesFreed.printCurrentVolume();
116      Log.write(" av: "); defragCleanBytesAvailable.printCurrentVolume();
117      Log.write(")");
118    }
119
120    inDefragCollection = false;
121    debugCollectionTypeDetermined = false;
122  }
123
124  int getDefragHeadroomPages() {
125    if (Options.defragHeadroom.getPages() > 0) {
126      return Options.defragHeadroom.getPages();
127    } else if (Options.defragHeadroomFraction.getValue() > 0) {
128      return (int) (pr.reservedPages() * Options.defragHeadroomFraction.getValue());
129    }
130    return 0;
131  }
132
133  void decideWhetherToDefrag(boolean emergencyCollection, boolean collectWholeHeap, int collectionAttempt, boolean userTriggered, boolean exhaustedReusableSpace) {
134    inDefragCollection =  (collectionAttempt > 1) ||
135        emergencyCollection ||
136        collectWholeHeap && (Options.defragStress.getValue() || (userTriggered && Options.fullHeapSystemGC.getValue()));
137    if (inDefragCollection) {
138      debugBytesDefraged = 0;
139    }
140    debugCollectionTypeDetermined = true;
141  }
142
143  boolean determined(boolean inDefrag) {
144    return debugCollectionTypeDetermined && !(inDefrag ^ inDefragCollection);
145  }
146
147  void getBlock() {
148    if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!inDefragCollection || !defragSpaceExhausted);
149    if (availableCleanPagesForDefrag <= 0)
150      defragSpaceExhausted = true;
151    availableCleanPagesForDefrag -= PAGES_IN_BLOCK;
152    debugBytesDefraged += BYTES_IN_BLOCK;
153    Defrag.defragCleanBytesUsed.inc(BYTES_IN_BLOCK);
154  }
155
156  private void establishDefragSpillThreshold(ChunkList chunkMap, ImmixSpace space) {
157    int cleanLines = space.getAvailableLines(spillAvailHistogram);
158    int availableLines = cleanLines + availableCleanPagesForDefrag << (LOG_BYTES_IN_PAGE - LOG_BYTES_IN_LINE);
159
160    int requiredLines = 0;
161    short threshold = MAX_CONSV_SPILL_COUNT;
162    int limit = (int) (availableLines / Options.defragLineReuseRatio.getValue());
163    if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() > 2) {
164      Log.write("[threshold: "); Log.write("cl: "); Log.write(cleanLines);
165      Log.write(" al: "); Log.write(availableLines);
166      Log.write(" lm: "); Log.write(limit);
167    }
168    int collectors = VM.activePlan.collectorCount();
169    for (short index = MAX_CONSV_SPILL_COUNT; index >= TMP_MIN_SPILL_THRESHOLD && limit > requiredLines; index--) {
170      threshold = index;
171      int thisBucketMark = 0;
172      int thisBucketAvail = 0;
173      for (int c = 0; c < collectors; c++) thisBucketMark += spillMarkHistograms[c][threshold];
174
175      thisBucketAvail = spillAvailHistogram[threshold];
176      limit -= thisBucketAvail;
177      requiredLines += thisBucketMark;
178      if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() > 2) {
179        Log.write(" ("); Log.write(index); Log.write(" "); Log.write(limit); Log.write(","); Log.write(requiredLines); Log.write(")");
180      }
181    }
182    if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() > 2) {
183      Log.write(" threshold: "); Log.write(threshold); Log.write("]");
184    }
185    defragSpillThreshold = threshold;
186  }
187
188
189  boolean spaceExhausted() {
190    return defragSpaceExhausted;
191  }
192
193  int[] getAndZeroSpillMarkHistogram(int ordinal) {
194    int[] rtn = spillMarkHistograms[ordinal];
195    for (int i = 0; i < SPILL_HISTOGRAM_BUCKETS; i++)
196      rtn[i] = 0;
197    return rtn;
198  }
199}