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.utility.heap;
014
015 import org.mmtk.policy.Space;
016 import org.mmtk.utility.GenericFreeList;
017 import org.mmtk.utility.Log;
018 import org.mmtk.utility.options.Options;
019 import org.mmtk.vm.Lock;
020 import org.mmtk.vm.VM;
021 import org.vmmagic.pragma.Inline;
022 import org.vmmagic.pragma.Interruptible;
023 import org.vmmagic.pragma.Uninterruptible;
024 import org.vmmagic.unboxed.Address;
025 import org.vmmagic.unboxed.Extent;
026 import org.vmmagic.unboxed.Word;
027
028 /**
029 * This class manages the mapping of spaces to virtual memory ranges.<p>
030 *
031 */
032 @Uninterruptible
033 public class Map {
034
035 /** set the map base address so that we have an unused {@code null} chunk at the bottome of the space for 64 bit */
036 private static final Address MAP_BASE_ADDRESS = Space.BITS_IN_ADDRESS == 32 ? Address.zero() : Space.HEAP_START.minus(Space.BYTES_IN_CHUNK);
037
038 /****************************************************************************
039 *
040 * Class variables
041 */
042
043 /**
044 *
045 */
046 private static final int[] descriptorMap;
047 private static final int[] prevLink;
048 private static final int[] nextLink;
049 private static final Space[] spaceMap;
050 private static final GenericFreeList regionMap;
051 public static final GenericFreeList globalPageMap;
052 private static int sharedDiscontigFLCount = 0;
053 private static final FreeListPageResource[] sharedFLMap;
054 private static int totalAvailableDiscontiguousChunks = 0;
055
056 private static final Lock lock = VM.newLock("Map lock");
057
058 /****************************************************************************
059 *
060 * Initialization
061 */
062
063 /**
064 * Class initializer. Create our two maps
065 */
066 static {
067 descriptorMap = new int[Space.MAX_CHUNKS];
068 prevLink = new int[Space.MAX_CHUNKS];
069 nextLink = new int[Space.MAX_CHUNKS];
070 spaceMap = new Space[Space.MAX_CHUNKS];
071 regionMap = new GenericFreeList(Space.MAX_CHUNKS);
072 globalPageMap = new GenericFreeList(1, 1, Space.MAX_SPACES);
073 sharedFLMap = new FreeListPageResource[Space.MAX_SPACES];
074 if (VM.VERIFY_ASSERTIONS)
075 VM.assertions._assert(Space.BITS_IN_ADDRESS == Space.LOG_ADDRESS_SPACE ||
076 Space.HEAP_END.diff(MAP_BASE_ADDRESS).toWord().rshl(Space.LOG_ADDRESS_SPACE).isZero());
077 }
078
079 /****************************************************************************
080 *
081 * Map accesses and insertion
082 */
083
084 /**
085 * Insert a space and its descriptor into the map, associating it
086 * with a particular address range.
087 *
088 * @param start The start address of the region to be associated
089 * with this space.
090 * @param extent The size of the region, in bytes
091 * @param descriptor The descriptor for this space
092 * @param space The space to be associated with this region
093 */
094 public static void insert(Address start, Extent extent, int descriptor,
095 Space space) {
096 Extent e = Extent.zero();
097 while (e.LT(extent)) {
098 int index = getChunkIndex(start.plus(e));
099 if (descriptorMap[index] != 0) {
100 Log.write("Conflicting virtual address request for space \"");
101 Log.write(space.getName()); Log.write("\" at ");
102 Log.writeln(start.plus(e));
103 Space.printVMMap();
104 VM.assertions.fail("exiting");
105 }
106 descriptorMap[index] = descriptor;
107 VM.barriers.objectArrayStoreNoGCBarrier(spaceMap, index, space);
108 e = e.plus(Space.BYTES_IN_CHUNK);
109 }
110 }
111
112 /**
113 * Allocate some number of contiguous chunks within a discontiguous region.
114 *
115 * @param descriptor The descriptor for the space to which these chunks will be assigned
116 * @param space The space to which these chunks will be assigned
117 * @param chunks The number of chunks required
118 * @param head The previous contiguous set of chunks for this space (to create a linked list of contiguous regions for each space)
119 * @return The address of the assigned memory. If the request fails we return Address.zero().
120 */
121 public static Address allocateContiguousChunks(int descriptor, Space space, int chunks, Address head) {
122 lock.acquire();
123 int chunk = regionMap.alloc(chunks);
124 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(chunk != 0);
125 if (chunk == -1) {
126 if (Options.verbose.getValue() > 3) {
127 Log.write("Unable to allocate virtual address space for space \"");
128 Log.write(space.getName()); Log.write("\" for ");
129 Log.write(chunks); Log.write(" chunks (");
130 Log.write(chunks<<Space.LOG_BYTES_IN_CHUNK); Log.writeln(" bytes), requesting GC.");
131 if (Options.verbose.getValue() > 7) {
132 Space.printVMMap();
133 }
134 }
135 lock.release();
136 return Address.zero();
137 }
138 totalAvailableDiscontiguousChunks -= chunks;
139 Address rtn = addressForChunkIndex(chunk);
140 insert(rtn, Extent.fromIntZeroExtend(chunks<<Space.LOG_BYTES_IN_CHUNK), descriptor, space);
141 if (head.isZero()) {
142 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(nextLink[chunk] == 0);
143 } else {
144 nextLink[chunk] = getChunkIndex(head);
145 prevLink[getChunkIndex(head)] = chunk;
146 }
147 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(prevLink[chunk] == 0);
148 lock.release();
149 return rtn;
150 }
151
152 /**
153 * Return the address of the next contiguous region associated with some discontiguous space by following the linked list for that space.
154 *
155 * @param start The current region (return the next region in the list)
156 * @return Return the next contiguous region after start in the linked list of regions
157 */
158 public static Address getNextContiguousRegion(Address start) {
159 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(start.EQ(Space.chunkAlign(start, true)));
160 int chunk = getChunkIndex(start);
161 return (chunk == 0) ? Address.zero() : (nextLink[chunk] == 0) ? Address.zero() : addressForChunkIndex(nextLink[chunk]);
162 }
163
164 /**
165 * Return the size of a contiguous region in chunks.
166 *
167 * @param start The start address of the region whose size is being requested
168 * @return The size of the region in question
169 */
170 public static int getContiguousRegionChunks(Address start) {
171 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(start.EQ(Space.chunkAlign(start, true)));
172 int chunk = getChunkIndex(start);
173 return regionMap.size(chunk);
174 }
175
176 /**
177 * Return the size of a contiguous region in bytes.
178 *
179 * @param start The start address of the region whose size is being requested
180 * @return The size of the region in question
181 */
182 public static Extent getContiguousRegionSize(Address start) {
183 return Word.fromIntSignExtend(getContiguousRegionChunks(start)).lsh(Space.LOG_BYTES_IN_CHUNK).toExtent();
184 }
185
186 /**
187 * Free all chunks in a linked list of contiguous chunks. This means starting
188 * with one and then walking the chains of contiguous regions, freeing each.
189 *
190 * @param anyChunk Any chunk in the linked list of chunks to be freed
191 */
192 public static void freeAllChunks(Address anyChunk) {
193 lock.acquire();
194 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(anyChunk.EQ(Space.chunkAlign(anyChunk, true)));
195 if (!anyChunk.isZero()) {
196 int chunk = getChunkIndex(anyChunk);
197 while (nextLink[chunk] != 0) {
198 freeContiguousChunks(nextLink[chunk]);
199 }
200 while (prevLink[chunk] != 0) {
201 freeContiguousChunks(prevLink[chunk]);
202 }
203 freeContiguousChunks(chunk);
204 }
205 lock.release();
206 }
207
208 /**
209 * Free some set of contiguous chunks, given the chunk address
210 *
211 * @param start The start address of the first chunk in the series
212 * @return The number of chunks which were contiguously allocated
213 */
214 public static int freeContiguousChunks(Address start) {
215 lock.acquire();
216 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(start.EQ(Space.chunkAlign(start, true)));
217 int rtn = freeContiguousChunks(getChunkIndex(start));
218 lock.release();
219 return rtn;
220 }
221
222 /**
223 * Free some set of contiguous chunks, given the chunk index
224 *
225 * @param chunk The chunk index of the region to be freed
226 * @return The number of chunks freed
227 */
228 private static int freeContiguousChunks(int chunk) {
229 int chunks = regionMap.free(chunk);
230 totalAvailableDiscontiguousChunks += chunks;
231 int next = nextLink[chunk];
232 int prev = prevLink[chunk];
233 if (next != 0) prevLink[next] = prev;
234 if (prev != 0) nextLink[prev] = next;
235 nextLink[chunk] = prevLink[chunk] = 0;
236 for (int offset = 0; offset < chunks; offset++) {
237 descriptorMap[chunk + offset] = 0;
238 VM.barriers.objectArrayStoreNoGCBarrier(spaceMap, chunk + offset, null);
239 }
240 return chunks;
241 }
242
243 /**
244 * Finalize the space map, establishing which virtual memory
245 * is nailed down, and then placing the rest into a map to
246 * be used by discontiguous spaces.
247 */
248 @Interruptible
249 public static void finalizeStaticSpaceMap() {
250 /* establish bounds of discontiguous space */
251 Address startAddress = Space.getDiscontigStart();
252 int firstChunk = getChunkIndex(startAddress);
253 int lastChunk = getChunkIndex(Space.getDiscontigEnd());
254 int unavailStartChunk = lastChunk + 1;
255 int trailingChunks = Space.MAX_CHUNKS - unavailStartChunk;
256 int pages = (1 + lastChunk - firstChunk) * Space.PAGES_IN_CHUNK;
257 globalPageMap.resizeFreeList(pages, pages);
258 for (int pr = 0; pr < sharedDiscontigFLCount; pr++)
259 sharedFLMap[pr].resizeFreeList(startAddress);
260
261 /* set up the region map free list */
262 int allocedChunk = regionMap.alloc(firstChunk); // block out entire bottom of address range
263 for (int chunkIndex = firstChunk; chunkIndex <= lastChunk; chunkIndex++)
264 allocedChunk = regionMap.alloc(1); // Tentatively allocate all usable chunks
265 allocedChunk = regionMap.alloc(trailingChunks); // block out entire top of address range
266 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(allocedChunk == unavailStartChunk);
267
268 /* set up the global page map and place chunks on free list */
269 int firstPage = 0;
270 for (int chunkIndex = firstChunk; chunkIndex <= lastChunk; chunkIndex++) {
271 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(spaceMap[chunkIndex] == null);
272 totalAvailableDiscontiguousChunks++;
273 regionMap.free(chunkIndex); // put this chunk on the free list
274 globalPageMap.setUncoalescable(firstPage);
275 int allocedPages = globalPageMap.alloc(Space.PAGES_IN_CHUNK); // populate the global page map
276 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(allocedPages == firstPage);
277 firstPage += Space.PAGES_IN_CHUNK;
278 }
279 }
280
281 /**
282 * Return the ordinal number for some free list space wishing to share a discontiguous region.
283 * @return The ordinal number for a free list space wishing to share a discontiguous region
284 */
285 @Interruptible
286 public static int getDiscontigFreeListPROrdinal(FreeListPageResource pr) {
287 sharedFLMap[sharedDiscontigFLCount] = pr;
288 sharedDiscontigFLCount++;
289 return sharedDiscontigFLCount;
290 }
291
292 /**
293 * Return the total number of chunks available (unassigned) within the
294 * range of virtual memory apportioned to discontiguous spaces.
295 *
296 * @return The number of available chunks for use by discontiguous spaces.
297 */
298 public static int getAvailableDiscontiguousChunks() {
299 return totalAvailableDiscontiguousChunks;
300 }
301
302 /**
303 * Return the total number of clients contending for chunks. This
304 * is useful when establishing conservative bounds on the number
305 * of remaining chunks.
306 *
307 * @return The total number of clients who may contend for chunks.
308 */
309 public static int getChunkConsumerCount() {
310 return sharedDiscontigFLCount;
311 }
312
313 /**
314 * Return the space in which this address resides.
315 *
316 * @param address The address in question
317 * @return The space in which the address resides
318 */
319 @Inline
320 public static Space getSpaceForAddress(Address address) {
321 int index = getChunkIndex(address);
322 return spaceMap[index];
323 }
324
325 /**
326 * Return the space descriptor for the space in which this object
327 * resides.
328 *
329 * @param object The object in question
330 * @return The space descriptor for the space in which the object
331 * resides
332 */
333 @Inline
334 public static int getDescriptorForAddress(Address object) {
335 int index = getChunkIndex(object);
336 return descriptorMap[index];
337 }
338
339 /**
340 * Hash an address to a chunk (this is simply done via bit shifting)
341 *
342 * @param address The address to be hashed
343 * @return The chunk number that this address hashes into
344 */
345 @Inline
346 private static int getChunkIndex(Address address) {
347 if (Space.BYTES_IN_ADDRESS == 8) {
348 if (address.LT(Space.HEAP_START) || address.GE(Space.HEAP_END))
349 return 0;
350 else
351 return address.diff(MAP_BASE_ADDRESS).toWord().rshl(Space.LOG_BYTES_IN_CHUNK).toInt();
352 } else
353 return address.toWord().rshl(Space.LOG_BYTES_IN_CHUNK).toInt();
354 }
355 @Inline
356 private static Address addressForChunkIndex(int chunk) {
357 if (Space.BYTES_IN_ADDRESS == 8) {
358 if (chunk == 0)
359 return Address.zero();
360 else
361 return MAP_BASE_ADDRESS.plus(Word.fromIntZeroExtend(chunk).lsh(Space.LOG_BYTES_IN_CHUNK).toExtent());
362 } else
363 return Word.fromIntZeroExtend(chunk).lsh(Space.LOG_BYTES_IN_CHUNK).toAddress();
364 }
365 }