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.plan.Plan;
016 import org.mmtk.policy.Space;
017 import static org.mmtk.policy.Space.PAGES_IN_CHUNK;
018 import org.mmtk.utility.alloc.EmbeddedMetaData;
019 import org.mmtk.utility.Conversions;
020 import org.mmtk.utility.GenericFreeList;
021 import org.mmtk.vm.VM;
022 import org.mmtk.utility.Constants;
023
024 import org.vmmagic.unboxed.*;
025 import org.vmmagic.pragma.*;
026
027 /**
028 * This class manages the allocation of pages for a space. When a
029 * page is requested by the space both a page budget and the use of
030 * virtual address space are checked. If the request for space can't
031 * be satisfied (for either reason) a GC may be triggered.<p>
032 */
033 @Uninterruptible
034 public final class FreeListPageResource extends PageResource implements Constants {
035
036 private final GenericFreeList freeList;
037 private int highWaterMark = 0;
038 private final int metaDataPagesPerRegion;
039 private int pagesCurrentlyOnFreeList = 0;
040
041 /**
042 * Constructor
043 *
044 * Contiguous free list resource. The address range is pre-defined at
045 * initialization time and is immutable.
046 *
047 * @param pageBudget The budget of pages available to this memory
048 * manager before it must poll the collector.
049 * @param space The space to which this resource is attached
050 * @param start The start of the address range allocated to this resource
051 * @param bytes The size of the address rage allocated to this resource
052 */
053 public FreeListPageResource(int pageBudget, Space space, Address start,
054 Extent bytes) {
055 super(pageBudget, space, start);
056 int pages = Conversions.bytesToPages(bytes);
057 freeList = new GenericFreeList(pages);
058 pagesCurrentlyOnFreeList = pages;
059 this.metaDataPagesPerRegion = 0;
060 }
061
062 /**
063 * Constructor
064 *
065 * Contiguous free list resource. The address range is pre-defined at
066 * initialization time and is immutable.
067 *
068 * @param pageBudget The budget of pages available to this memory
069 * manager before it must poll the collector.
070 * @param space The space to which this resource is attached
071 * @param start The start of the address range allocated to this resource
072 * @param bytes The size of the address rage allocated to this resource
073 * @param metaDataPagesPerRegion The number of pages of meta data
074 * that are embedded in each region.
075 */
076 public FreeListPageResource(int pageBudget, Space space, Address start,
077 Extent bytes, int metaDataPagesPerRegion) {
078 super(pageBudget, space, start);
079 this.metaDataPagesPerRegion = metaDataPagesPerRegion;
080 int pages = Conversions.bytesToPages(bytes);
081 freeList = new GenericFreeList(pages, EmbeddedMetaData.PAGES_IN_REGION);
082 pagesCurrentlyOnFreeList = pages;
083 reserveMetaData(space.getExtent());
084 }
085
086 /**
087 * Constructor
088 *
089 * Discontiguous monotone resource. The address range is <i>not</i>
090 * pre-defined at initialization time and is dynamically defined to
091 * be some set of pages, according to demand and availability.
092 *
093 * @param pageBudget The budget of pages available to this memory
094 * manager before it must poll the collector.
095 * @param space The space to which this resource is attached
096 */
097 public FreeListPageResource(int pageBudget, Space space, int metaDataPagesPerRegion) {
098 super(pageBudget, space);
099 this.metaDataPagesPerRegion = metaDataPagesPerRegion;
100 this.start = Space.AVAILABLE_START;
101 freeList = new GenericFreeList(Map.globalPageMap, Map.getDiscontigFreeListPROrdinal(this));
102 pagesCurrentlyOnFreeList = 0;
103 }
104
105 /**
106 * Return the number of available physical pages for this resource.
107 * This includes all pages currently free on the resource's free list.
108 * If the resource is using discontiguous space it also includes
109 * currently unassigned discontiguous space.<p>
110 *
111 * Note: This just considers physical pages (ie virtual memory pages
112 * allocated for use by this resource). This calculation is orthogonal
113 * to and does not consider any restrictions on the number of pages
114 * this resource may actually use at any time (ie the number of
115 * committed and reserved pages).<p>
116 *
117 * Note: The calculation is made on the assumption that all space that
118 * could be assigned to this resource would be assigned to this resource
119 * (ie the unused discontiguous space could just as likely be assigned
120 * to another competing resource).
121 *
122 * @return The number of available physical pages for this resource.
123 */
124 @Override
125 public int getAvailablePhysicalPages() {
126 int rtn = pagesCurrentlyOnFreeList;
127 if (!contiguous) {
128 int chunks = Map.getAvailableDiscontiguousChunks()-Map.getChunkConsumerCount();
129 if (chunks < 0) chunks = 0;
130 rtn += chunks*(Space.PAGES_IN_CHUNK-metaDataPagesPerRegion);
131 }
132 return rtn;
133 }
134
135 /**
136 * Allocate <code>pages</code> pages from this resource.<p>
137 *
138 * If the request can be satisfied, then ensure the pages are
139 * mmpapped and zeroed before returning the address of the start of
140 * the region. If the request cannot be satisfied, return zero.
141 *
142 * @param pages The number of pages to be allocated.
143 * @return The start of the first page if successful, zero on
144 * failure.
145 */
146 @Inline
147 protected Address allocPages(int pages) {
148 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(metaDataPagesPerRegion == 0 || pages <= PAGES_IN_CHUNK - metaDataPagesPerRegion);
149 lock();
150 boolean newChunk = false;
151 int pageOffset = freeList.alloc(pages);
152 if (pageOffset == GenericFreeList.FAILURE && !contiguous) {
153 pageOffset = allocateContiguousChunks(pages);
154 newChunk = true;
155 }
156 if (pageOffset == -1) {
157 unlock();
158 return Address.zero();
159 } else {
160 pagesCurrentlyOnFreeList -= pages;
161 if (pageOffset > highWaterMark) {
162 if (highWaterMark == 0 || (pageOffset ^ highWaterMark) > EmbeddedMetaData.PAGES_IN_REGION) {
163 int regions = 1 + ((pageOffset - highWaterMark) >> EmbeddedMetaData.LOG_PAGES_IN_REGION);
164 int metapages = regions * metaDataPagesPerRegion;
165 reserved += metapages;
166 committed += metapages;
167 newChunk = true;
168 }
169 highWaterMark = pageOffset;
170 }
171 Address rtn = start.plus(Conversions.pagesToBytes(pageOffset));
172 Extent bytes = Conversions.pagesToBytes(pages);
173 commitPages(pages, pages);
174 space.growSpace(rtn, bytes, newChunk);
175 unlock();
176 Mmapper.ensureMapped(rtn, pages);
177 VM.memory.zero(rtn, bytes);
178 VM.events.tracePageAcquired(space, rtn, pages);
179 return rtn;
180 }
181 }
182
183 /**
184 * Release a group of pages, associated with this page resource,
185 * that were allocated together, optionally zeroing on release and
186 * optionally memory protecting on release.
187 *
188 * @param first The first page in the group of pages that were
189 * allocated together.
190 */
191 @Inline
192 public void releasePages(Address first) {
193 if (VM.VERIFY_ASSERTIONS)
194 VM.assertions._assert(Conversions.isPageAligned(first));
195
196 int pageOffset = Conversions.bytesToPages(first.diff(start));
197
198 int pages = freeList.size(pageOffset);
199 if (ZERO_ON_RELEASE)
200 VM.memory.zero(first, Conversions.pagesToBytes(pages));
201 /* Can't use protect here because of the chunk sizes involved!
202 if (protectOnRelease.getValue())
203 LazyMmapper.protect(first, pages);
204 */
205 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(pages <= committed);
206
207 lock();
208 reserved -= pages;
209 committed -= pages;
210 int freed = freeList.free(pageOffset, true);
211 pagesCurrentlyOnFreeList += pages;
212
213 if (!contiguous) // only discontiguous spaces use chunks
214 releaseFreeChunks(first, freed);
215
216 unlock();
217
218 VM.events.tracePageReleased(space, first, pages);
219 }
220
221 /**
222 * The release of a page may have freed up an entire chunk or
223 * set of chunks. We need to check whether any chunks can be
224 * freed, and if so, free them.
225 *
226 * @param freedPage The address of the page that was just freed.
227 * @param pagesFreed The number of pages made available when the page was freed.
228 */
229 private void releaseFreeChunks(Address freedPage, int pagesFreed) {
230 int pageOffset = Conversions.bytesToPages(freedPage.diff(start));
231
232 if (metaDataPagesPerRegion > 0) { // can only be a single chunk
233 if (pagesFreed == (PAGES_IN_CHUNK - metaDataPagesPerRegion)) {
234 freeContiguousChunk(Space.chunkAlign(freedPage, true));
235 }
236 } else { // may be multiple chunks
237 if (pagesFreed % PAGES_IN_CHUNK == 0) { // necessary, but not sufficient condition
238 /* grow a region of chunks, starting with the chunk containing the freed page */
239 int regionStart = pageOffset & ~(PAGES_IN_CHUNK - 1);
240 int nextRegionStart = regionStart + PAGES_IN_CHUNK;
241 /* now try to grow (end point pages are marked as non-coalescing) */
242 while (regionStart >= 0 && freeList.isCoalescable(regionStart))
243 regionStart -= PAGES_IN_CHUNK;
244 while (nextRegionStart < GenericFreeList.MAX_UNITS && freeList.isCoalescable(nextRegionStart))
245 nextRegionStart += PAGES_IN_CHUNK;
246 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(regionStart >= 0 && nextRegionStart < GenericFreeList.MAX_UNITS);
247 if (pagesFreed == nextRegionStart - regionStart) {
248 freeContiguousChunk(start.plus(Conversions.pagesToBytes(regionStart)));
249 }
250 }
251 }
252 }
253
254 /**
255 * Allocate sufficient contiguous chunks within a discontiguous region to
256 * satisfy the pending request. Note that this is purely about address space
257 * allocation within a discontiguous region. This method does not reserve
258 * individual pages, it merely assigns a suitably large region of virtual
259 * memory from within the discontiguous region for use by a particular space.
260 *
261 * @param pages The number of pages currently being requested
262 * @return A chunk number or GenericFreelist.FAILURE
263 */
264 private int allocateContiguousChunks(int pages) {
265 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(metaDataPagesPerRegion == 0 || pages <= PAGES_IN_CHUNK - metaDataPagesPerRegion);
266 int rtn = GenericFreeList.FAILURE;
267 int requiredChunks = Space.requiredChunks(pages);
268 Address region = space.growDiscontiguousSpace(requiredChunks);
269 if (!region.isZero()) {
270 int regionStart = Conversions.bytesToPages(region.diff(start));
271 int regionEnd = regionStart + (requiredChunks*Space.PAGES_IN_CHUNK) - 1;
272 freeList.setUncoalescable(regionStart);
273 freeList.setUncoalescable(regionEnd + 1);
274 for (int p = regionStart; p < regionEnd; p += Space.PAGES_IN_CHUNK) {
275 int liberated;
276 if (p != regionStart)
277 freeList.clearUncoalescable(p);
278 liberated = freeList.free(p, true); // add chunk to our free list
279 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(liberated == Space.PAGES_IN_CHUNK + (p - regionStart));
280 if (metaDataPagesPerRegion > 1)
281 freeList.alloc(metaDataPagesPerRegion, p); // carve out space for metadata
282 pagesCurrentlyOnFreeList += Space.PAGES_IN_CHUNK - metaDataPagesPerRegion;
283 }
284 rtn = freeList.alloc(pages); // re-do the request which triggered this call
285 }
286 return rtn;
287 }
288
289 /**
290 * Release a single chunk from a discontiguous region. All this does is
291 * release a chunk from the virtual address space associated with this
292 * discontiguous space.
293 *
294 * @param chunk The chunk to be freed
295 */
296 private void freeContiguousChunk(Address chunk) {
297 int numChunks = Map.getContiguousRegionChunks(chunk);
298 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(numChunks == 1 || metaDataPagesPerRegion == 0);
299
300 /* nail down all pages associated with the chunk, so it is no longer on our free list */
301 int chunkStart = Conversions.bytesToPages(chunk.diff(start));
302 int chunkEnd = chunkStart + (numChunks*Space.PAGES_IN_CHUNK);
303 while (chunkStart < chunkEnd) {
304 freeList.setUncoalescable(chunkStart);
305 if (metaDataPagesPerRegion > 0)
306 freeList.free(chunkStart); // first free any metadata pages
307 int tmp = freeList.alloc(Space.PAGES_IN_CHUNK, chunkStart); // then alloc the entire chunk
308 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(tmp == chunkStart);
309 chunkStart += Space.PAGES_IN_CHUNK;
310 pagesCurrentlyOnFreeList -= (Space.PAGES_IN_CHUNK - metaDataPagesPerRegion);
311 }
312 /* now return the address space associated with the chunk for global reuse */
313 space.releaseDiscontiguousChunks(chunk);
314 }
315
316 /**
317 * Reserve virtual address space for meta-data.
318 *
319 * @param extent The size of this space
320 */
321 private void reserveMetaData(Extent extent) {
322 highWaterMark = 0;
323 if (metaDataPagesPerRegion > 0) {
324 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(start.toWord().rshl(EmbeddedMetaData.LOG_BYTES_IN_REGION).lsh(EmbeddedMetaData.LOG_BYTES_IN_REGION).toAddress().EQ(start));
325 Extent size = extent.toWord().rshl(EmbeddedMetaData.LOG_BYTES_IN_REGION).lsh(EmbeddedMetaData.LOG_BYTES_IN_REGION).toExtent();
326 Address cursor = start.plus(size);
327 while (cursor.GT(start)) {
328 cursor = cursor.minus(EmbeddedMetaData.BYTES_IN_REGION);
329 int unit = cursor.diff(start).toWord().rshl(LOG_BYTES_IN_PAGE).toInt();
330 int tmp = freeList.alloc(metaDataPagesPerRegion, unit);
331 pagesCurrentlyOnFreeList -= metaDataPagesPerRegion;
332 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(tmp == unit);
333 }
334 }
335 }
336
337 /**
338 * Adjust a page request to include metadata requirements, if any. In the
339 * case of a free-list allocator, meta-data is pre-allocated, so simply
340 * return the un-adjusted request size.
341 *
342 * @param pages The size of the pending allocation in pages
343 * @return The (unadjusted) request size, since metadata is pre-allocated
344 */
345 public int adjustForMetaData(int pages) { return pages; }
346
347 public Address getHighWater() {
348 return start.plus(Extent.fromIntSignExtend(highWaterMark<<LOG_BYTES_IN_PAGE));
349 }
350
351 /**
352 * Return the size of the super page
353 *
354 * @param first the Address of the first word in the superpage
355 * @return the size in bytes
356 */
357 @Inline
358 public Extent getSize(Address first) {
359 if (VM.VERIFY_ASSERTIONS)
360 VM.assertions._assert(Conversions.isPageAligned(first));
361
362 int pageOffset = Conversions.bytesToPages(first.diff(start));
363 int pages = freeList.size(pageOffset);
364 return Conversions.pagesToBytes(pages);
365 }
366
367 /**
368 * Resize the free list associated with this resource and nail down
369 * its start address. This method is called to re-set the free list
370 * once the global free list (which it shares) is finalized and the
371 * base address is finalized. There's a circular dependency, so we
372 * need an explicit call-back to reset the free list size and start
373 *
374 * @param startAddress The final start address for the discontiguous space.
375 */
376 @Interruptible
377 public void resizeFreeList(Address startAddress) {
378 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!contiguous && !Plan.isInitialized());
379 start = startAddress;
380 freeList.resizeFreeList();
381 }
382 }