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.mmtk.policy.immix;
014
015 import org.mmtk.plan.Plan;
016 import org.mmtk.policy.Space;
017 import org.mmtk.utility.Constants;
018 import org.mmtk.vm.VM;
019 import org.vmmagic.pragma.Uninterruptible;
020 import org.vmmagic.unboxed.Address;
021 import org.vmmagic.unboxed.AddressArray;
022
023 @Uninterruptible
024 public final class ChunkList implements Constants {
025 private static final int LOG_PAGES_IN_CHUNK_MAP_BLOCK = 0;
026 private static final int ENTRIES_IN_CHUNK_MAP_BLOCK = (BYTES_IN_PAGE<<LOG_PAGES_IN_CHUNK_MAP_BLOCK)>>LOG_BYTES_IN_ADDRESS;
027 private static final int CHUNK_MAP_BLOCKS = 1<<4;
028 private static final int MAX_ENTRIES_IN_CHUNK_MAP = ENTRIES_IN_CHUNK_MAP_BLOCK * CHUNK_MAP_BLOCKS;
029 private AddressArray chunkMap = AddressArray.create(CHUNK_MAP_BLOCKS);
030 private int chunkMapLimit = -1;
031 private int chunkMapCursor = -1;
032
033 void reset() {
034 chunkMapLimit = chunkMapCursor;
035 }
036
037 public Address getHeadChunk() {
038 if (chunkMapLimit < 0)
039 return Address.zero();
040 else
041 return getMapAddress(0).loadAddress();
042 }
043
044 public Address getTailChunk() {
045 if (chunkMapLimit < 0)
046 return Address.zero();
047 else
048 return getMapAddress(chunkMapLimit).loadAddress();
049 }
050
051 void addNewChunkToMap(Address chunk) {
052 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(Chunk.isAligned(chunk));
053 if (chunkMapCursor == MAX_ENTRIES_IN_CHUNK_MAP - 1)
054 consolidateMap();
055 chunkMapCursor++;
056 int index = getChunkIndex(chunkMapCursor);
057 int map = getChunkMap(chunkMapCursor);
058 if (map >= CHUNK_MAP_BLOCKS) {
059 Space.printUsageMB();
060 VM.assertions.fail("Overflow of chunk map!");
061 }
062 if (chunkMap.get(map).isZero()) {
063 Address tmp = Plan.metaDataSpace.acquire(1<<LOG_PAGES_IN_CHUNK_MAP_BLOCK);
064 if (tmp.isZero()) {
065 Space.printUsageMB();
066 VM.assertions.fail("Failed to allocate space for chunk map. Is metadata virtual memory exhausted?");
067 }
068 chunkMap.set(map, tmp);
069 }
070 Address entry = chunkMap.get(map).plus(index<<LOG_BYTES_IN_ADDRESS);
071 entry.store(chunk);
072 Chunk.setMap(chunk, chunkMapCursor);
073 if (VM.VERIFY_ASSERTIONS) checkMap();
074 }
075
076 void removeChunkFromMap(Address chunk) {
077 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(Chunk.isAligned(chunk));
078 int entry = Chunk.getMap(chunk);
079 getMapAddress(entry).store(Address.zero()); // zero it it
080 Chunk.setMap(chunk, -entry);
081 if (VM.VERIFY_ASSERTIONS) checkMap();
082 }
083
084 private int getChunkIndex(int entry) { return entry & (ENTRIES_IN_CHUNK_MAP_BLOCK - 1);}
085 private int getChunkMap(int entry) {return entry & ~(ENTRIES_IN_CHUNK_MAP_BLOCK - 1);}
086
087 private Address getMapAddress(int entry) {
088 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(entry >= 0);
089 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(entry <= chunkMapCursor);
090 int index = getChunkIndex(entry);
091 int map = getChunkMap(entry);
092 return chunkMap.get(map).plus(index<<LOG_BYTES_IN_ADDRESS);
093 }
094
095 /**
096 * A chunk iterator. Return the next chunk in sequence, or null if the
097 * next chunk is the same chunk (ie there is only one chunk in the iterator).
098 *
099 * @param chunk The chunk
100 * @return The next chunk in the sequence, or null if next is chunk.
101 */
102 public Address nextChunk(Address chunk) {
103 return nextChunk(chunk, chunk);
104 }
105
106 /**
107 * A chunk iterator. Return the next chunk in sequence, or {@code null} if the
108 * next chunk is limit.
109 *
110 * @param chunk The chunk
111 * @param limit The starting point (if next is equal to this, we're done)
112 * @return The next chunk in the sequence, or {@code null} if next is limit.
113 */
114 private Address nextChunk(final Address chunk, final Address limit) {
115 return nextChunk(chunk, Chunk.getMap(limit), 1);
116 }
117
118 /**
119 * A chunk iterator. Return the next chunk in sequence, strided
120 * by stride steps, or {@code null} if the next chunk is start.
121 *
122 * @param chunk The chunk
123 * @param start The point where this iterator started, which defines its end-point
124 * @param stride The stride by which the iterator should be stepped
125 * @return The next chunk in the sequence, or {@code null} if next is start.
126 */
127 public Address nextChunk(final Address chunk, final int start, final int stride) {
128 if (VM.VERIFY_ASSERTIONS) checkMap();
129 return nextChunk(Chunk.getMap(chunk), start, stride);
130 }
131
132 /**
133 * A chunk iterator. Return the next chunk in sequence, strided
134 * by stride steps, or {@code null} if the next chunk is start.
135 *
136 * @param entry The entry we're currently up to
137 * @param start The point where this iterator started, which defines its end-point
138 * @param stride The stride by which the iterator should be stepped
139 * @return The next chunk in the sequence, or {@code null} if next is start.
140 */
141 private Address nextChunk(int entry, final int start, final int stride) {
142 if (VM.VERIFY_ASSERTIONS) checkMap();
143 Address chunk;
144 do {
145 entry += stride;
146 if (entry > chunkMapLimit) { entry = entry % stride; }
147 chunk = getMapAddress(entry).loadAddress();
148 } while (chunk.isZero() && entry != start);
149 return entry == start ? Address.zero() : chunk;
150 }
151
152 public Address firstChunk(int ordinal, int stride) {
153 if (ordinal > chunkMapCursor) return Address.zero();
154 if (VM.VERIFY_ASSERTIONS) checkMap();
155 Address chunk = getMapAddress(ordinal).loadAddress();
156 return chunk.isZero() ? nextChunk(ordinal, ordinal, stride) : chunk;
157 }
158
159 private void checkMap() {
160 VM.assertions._assert(chunkMapLimit <= chunkMapCursor);
161 for (int entry = 0; entry <= chunkMapCursor; entry++) {
162 Address chunk = getMapAddress(entry).loadAddress();
163 if (!chunk.isZero())
164 VM.assertions._assert(Chunk.getMap(chunk) == entry);
165 }
166 }
167
168 public void consolidateMap() {
169 int oldCursor = 0;
170 int newCursor = -1;
171 while (oldCursor <= chunkMapCursor) {
172 Address chunk = getMapAddress(oldCursor).loadAddress();
173 if (!chunk.isZero()) {
174 getMapAddress(++newCursor).store(chunk);
175 Chunk.setMap(chunk, newCursor);
176 }
177 oldCursor++;
178 }
179 chunkMapCursor = newCursor;
180 chunkMapLimit = newCursor;
181 if (VM.VERIFY_ASSERTIONS) checkMap();
182 }
183 }