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