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.alloc;
014
015 import org.mmtk.policy.Space;
016 import org.mmtk.utility.Constants;
017 import org.mmtk.utility.Conversions;
018 import org.mmtk.utility.Log;
019 import org.mmtk.utility.gcspy.drivers.LinearSpaceDriver;
020 import org.mmtk.vm.VM;
021 import org.vmmagic.pragma.Inline;
022 import org.vmmagic.pragma.NoInline;
023 import org.vmmagic.pragma.Uninterruptible;
024 import org.vmmagic.unboxed.Address;
025 import org.vmmagic.unboxed.Extent;
026 import org.vmmagic.unboxed.ObjectReference;
027 import org.vmmagic.unboxed.Offset;
028 import org.vmmagic.unboxed.Word;
029
030 /**
031 * This class implements a bump pointer allocator that allows linearly
032 * scanning through the allocated objects. In order to achieve this in the
033 * face of parallelism it maintains a header at a region (1 or more blocks)
034 * granularity.
035 *
036 * Intra-block allocation is fast, requiring only a load, addition comparison
037 * and store. If a block boundary is encountered the allocator will
038 * request more memory (virtual and actual).
039 *
040 * In the current implementation the scanned objects maintain affinity
041 * with the thread that allocated the objects in the region. In the future
042 * it is anticipated that subclasses should be allowed to choose to improve
043 * load balancing during the parallel scan.
044 *
045 * Each region is laid out as follows:
046 *
047 * +-------------+-------------+-------------+---------------
048 * | Region End | Next Region | Data End | Data -->
049 * +-------------+-------------+-------------+---------------
050 *
051 * The minimum region size is 32768 bytes, so the 3 or 4 word overhead is
052 * less than 0.05% of all space.
053 *
054 * An intended enhancement is to facilitate a reallocation operation
055 * where a second cursor is maintained over earlier regions (and at the
056 * limit a lower location in the same region). This would be accompianied
057 * with an alternative slow path that would allow reuse of empty regions.
058 *
059 * This class relies on the supporting virtual machine implementing the
060 * getNextObject and related operations.
061 */
062 @Uninterruptible public class BumpPointer extends Allocator
063 implements Constants {
064
065 /****************************************************************************
066 *
067 * Class variables
068 */
069
070 // Block size defines slow path periodicity.
071 private static final int LOG_DEFAULT_STEP_SIZE = 30; // 1G: let the external slow path dominate
072 private static final int STEP_SIZE = 1<<(SUPPORT_CARD_SCANNING ? LOG_CARD_BYTES : LOG_DEFAULT_STEP_SIZE);
073 protected static final int LOG_BLOCK_SIZE = LOG_BYTES_IN_PAGE + 3;
074 protected static final Word BLOCK_MASK = Word.one().lsh(LOG_BLOCK_SIZE).minus(Word.one());
075 private static final int BLOCK_SIZE = (1<<LOG_BLOCK_SIZE);
076
077
078 // Offsets into header
079 protected static final Offset REGION_LIMIT_OFFSET = Offset.zero();
080 protected static final Offset NEXT_REGION_OFFSET = REGION_LIMIT_OFFSET.plus(BYTES_IN_ADDRESS);
081 protected static final Offset DATA_END_OFFSET = NEXT_REGION_OFFSET.plus(BYTES_IN_ADDRESS);
082
083 // Data must start particle-aligned.
084 protected static final Offset DATA_START_OFFSET = alignAllocationNoFill(
085 Address.zero().plus(DATA_END_OFFSET.plus(BYTES_IN_ADDRESS)),
086 MIN_ALIGNMENT, 0).toWord().toOffset();
087 protected static final Offset MAX_DATA_START_OFFSET = alignAllocationNoFill(
088 Address.zero().plus(DATA_END_OFFSET.plus(BYTES_IN_ADDRESS)),
089 MAX_ALIGNMENT, 0).toWord().toOffset();
090
091 public static final int MINIMUM_DATA_SIZE = (1 << LOG_BLOCK_SIZE) - MAX_DATA_START_OFFSET.toInt();
092
093 private static final boolean VERBOSE = false;
094
095 /****************************************************************************
096 *
097 * Instance variables
098 */
099 protected Address cursor; // insertion point
100 private Address internalLimit; // current internal slow-path sentinal for bump pointer
101 private Address limit; // current external slow-path sentinal for bump pointer
102 protected Space space; // space this bump pointer is associated with
103 protected Address initialRegion; // first contiguous region
104 protected final boolean allowScanning; // linear scanning is permitted if true
105 protected Address region; // current contiguous region
106
107
108 /**
109 * Constructor.
110 *
111 * @param space The space to bump point into.
112 * @param allowScanning Allow linear scanning of this region of memory.
113 */
114 protected BumpPointer(Space space, boolean allowScanning) {
115 this.space = space;
116 this.allowScanning = allowScanning;
117 reset();
118 }
119
120 /**
121 * Reset the allocator. Note that this does not reset the space.
122 * This is must be done by the caller.
123 */
124 public final void reset() {
125 cursor = Address.zero();
126 limit = Address.zero();
127 internalLimit = Address.zero();
128 initialRegion = Address.zero();
129 region = Address.zero();
130 }
131
132 /**
133 * Re-associate this bump pointer with a different space. Also
134 * reset the bump pointer so that it will use the new space
135 * on the next call to <code>alloc</code>.
136 *
137 * @param space The space to associate the bump pointer with.
138 */
139 public final void rebind(Space space) {
140 reset();
141 this.space = space;
142 }
143
144 /**
145 * Allocate space for a new object. This is frequently executed code and
146 * the coding is deliberaetly sensitive to the optimizing compiler.
147 * After changing this, always check the IR/MC that is generated.
148 *
149 * @param bytes The number of bytes allocated
150 * @param align The requested alignment
151 * @param offset The offset from the alignment
152 * @return The address of the first byte of the allocated region
153 */
154 @Inline
155 public final Address alloc(int bytes, int align, int offset) {
156 Address start = alignAllocationNoFill(cursor, align, offset);
157 Address end = start.plus(bytes);
158 if (end.GT(internalLimit))
159 return allocSlow(start, end, align, offset);
160 fillAlignmentGap(cursor, start);
161 cursor = end;
162 return start;
163 }
164
165 /**
166 * Internal allocation slow path. This is called whenever the bump
167 * pointer reaches the internal limit. The code is forced out of
168 * line. If required we perform an external slow path take, which
169 * we inline into this method since this is already out of line.
170 *
171 * @param start The start address for the pending allocation
172 * @param end The end address for the pending allocation
173 * @param align The requested alignment
174 * @param offset The offset from the alignment
175 * @return The address of the first byte of the allocated region
176 */
177 @NoInline
178 private Address allocSlow(Address start, Address end, int align,
179 int offset) {
180 Address rtn = null;
181 Address card = null;
182 if (SUPPORT_CARD_SCANNING)
183 card = getCard(start.plus(CARD_MASK)); // round up
184 if (end.GT(limit)) { /* external slow path */
185 rtn = allocSlowInline(end.diff(start).toInt(), align, offset);
186 if (SUPPORT_CARD_SCANNING && card.NE(getCard(rtn.plus(CARD_MASK))))
187 card = getCard(rtn); // round down
188 } else { /* internal slow path */
189 while (internalLimit.LE(end))
190 internalLimit = internalLimit.plus(STEP_SIZE);
191 if (internalLimit.GT(limit))
192 internalLimit = limit;
193 fillAlignmentGap(cursor, start);
194 cursor = end;
195 rtn = start;
196 }
197 if (SUPPORT_CARD_SCANNING && !rtn.isZero())
198 createCardAnchor(card, rtn, end.diff(start).toInt());
199 return rtn;
200 }
201
202 /**
203 * Given an allocation which starts a new card, create a record of
204 * where the start of the object is relative to the start of the
205 * card.
206 *
207 * @param card An address that lies within the card to be marked
208 * @param start The address of an object which creates a new card.
209 * @param bytes The size of the pending allocation in bytes (used for debugging)
210 */
211 private void createCardAnchor(Address card, Address start, int bytes) {
212 if (VM.VERIFY_ASSERTIONS) {
213 VM.assertions._assert(allowScanning);
214 VM.assertions._assert(card.EQ(getCard(card)));
215 VM.assertions._assert(start.diff(card).sLE(MAX_DATA_START_OFFSET));
216 VM.assertions._assert(start.diff(card).toInt() >= -CARD_MASK);
217 }
218 while (bytes > 0) {
219 int offset = start.diff(card).toInt();
220 getCardMetaData(card).store(offset);
221 card = card.plus(1 << LOG_CARD_BYTES);
222 bytes -= (1 << LOG_CARD_BYTES);
223 }
224 }
225
226 /**
227 * Return the start of the card corresponding to a given address.
228 *
229 * @param address The address for which the card start is required
230 * @return The start of the card containing the address
231 */
232 private static Address getCard(Address address) {
233 return address.toWord().and(Word.fromIntSignExtend(CARD_MASK).not()).toAddress();
234 }
235
236 /**
237 * Return the address of the metadata for a card, given the address of the card.
238 * @param card The address of some card
239 * @return The address of the metadata associated with that card
240 */
241 private static Address getCardMetaData(Address card) {
242 Address metadata = EmbeddedMetaData.getMetaDataBase(card);
243 return metadata.plus(EmbeddedMetaData.getMetaDataOffset(card, LOG_CARD_BYTES-LOG_CARD_META_SIZE, LOG_CARD_META_SIZE));
244 }
245
246 /**
247 * External allocation slow path (called by superclass when slow path is
248 * actually taken. This is necessary (rather than a direct call
249 * from the fast path) because of the possibility of a thread switch
250 * and corresponding re-association of bump pointers to kernel
251 * threads.
252 *
253 * @param bytes The number of bytes allocated
254 * @param offset The offset from the alignment
255 * @param align The requested alignment
256 * @return The address of the first byte of the allocated region or
257 * zero on failure
258 */
259 @Override
260 protected final Address allocSlowOnce(int bytes, int align, int offset) {
261 /* Check we have been bound to a space */
262 if (space == null) {
263 VM.assertions.fail("Allocation on unbound bump pointer.");
264 }
265
266 /* Check if we already have a block to use */
267 if (allowScanning && !region.isZero()) {
268 Address nextRegion = getNextRegion(region);
269 if (!nextRegion.isZero()) {
270 return consumeNextRegion(nextRegion, bytes, align, offset);
271 }
272 }
273
274 /* Acquire space, block aligned, that can accommodate the request */
275 Extent blockSize = Word.fromIntZeroExtend(bytes).plus(BLOCK_MASK)
276 .and(BLOCK_MASK.not()).toExtent();
277 Address start = space.acquire(Conversions.bytesToPages(blockSize));
278
279 if (start.isZero()) return start; // failed allocation
280
281 if (!allowScanning) { // simple allocator
282 if (start.NE(limit)) cursor = start; // discontiguous
283 updateLimit(start.plus(blockSize), start, bytes);
284 } else // scannable allocator
285 updateMetaData(start, blockSize, bytes);
286 return alloc(bytes, align, offset);
287 }
288
289 /**
290 * Update the limit pointer. As a side effect update the internal limit
291 * pointer appropriately.
292 *
293 * @param newLimit The new value for the limit pointer
294 * @param start The start of the region to be allocated into
295 * @param bytes The size of the pending allocation (if any).
296 */
297 @Inline
298 protected final void updateLimit(Address newLimit, Address start, int bytes) {
299 limit = newLimit;
300 internalLimit = start.plus(STEP_SIZE);
301 if (internalLimit.GT(limit))
302 internalLimit = limit;
303 else {
304 while (internalLimit.LT(cursor.plus(bytes)))
305 internalLimit = internalLimit.plus(STEP_SIZE);
306 if (VM.VERIFY_ASSERTIONS)
307 VM.assertions._assert(internalLimit.LE(limit));
308 }
309 }
310
311 /**
312 * A bump pointer chunk/region has been consumed but the contiguous region
313 * is available, so consume it and then return the address of the start
314 * of a memory region satisfying the outstanding allocation request. This
315 * is relevant when re-using memory, as in a mark-compact collector.
316 *
317 * @param nextRegion The region to be consumed
318 * @param bytes The number of bytes allocated
319 * @param align The requested alignment
320 * @param offset The offset from the alignment
321 * @return The address of the first byte of the allocated region or
322 * zero on failure
323 */
324 private Address consumeNextRegion(Address nextRegion, int bytes, int align,
325 int offset) {
326 setNextRegion(region,cursor);
327 region = nextRegion;
328 cursor = getDataStart(nextRegion);
329 updateLimit(getRegionLimit(nextRegion), nextRegion, bytes);
330 setDataEnd(nextRegion,Address.zero());
331 VM.memory.zero(cursor, limit.diff(cursor).toWord().toExtent());
332 reusePages(Conversions.bytesToPages(limit.diff(region)));
333
334 return alloc(bytes, align, offset);
335 }
336
337 /******************************************************************************
338 *
339 * Accessor methods for the region metadata fields.
340 *
341 */
342
343 /**
344 * The first offset in a region after the header
345 * @param region The region
346 * @return The lowest address at which data can be stored
347 */
348 @Inline
349 public static Address getDataStart(Address region) {
350 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!region.isZero());
351 return region.plus(DATA_START_OFFSET);
352 }
353
354 /**
355 * The next region in the linked-list of regions
356 * @param region The region
357 * @return The next region in the list
358 */
359 @Inline
360 public static Address getNextRegion(Address region) {
361 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!region.isZero());
362 Address result = region.plus(NEXT_REGION_OFFSET).loadAddress();
363 return result;
364 }
365
366 /**
367 * Set the next region in the linked-list of regions
368 * @param region The region
369 * @param the next region in the list
370 */
371 @Inline
372 public static void setNextRegion(Address region, Address nextRegion) {
373 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!region.isZero());
374 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!nextRegion.EQ(Address.fromIntZeroExtend(0xdeadbeef)));
375 region.store(nextRegion,NEXT_REGION_OFFSET);
376 }
377
378 /**
379 * Clear the next region pointer in the linked-list of regions
380 * @param region The region
381 */
382 @Inline
383 public static void clearNextRegion(Address region) {
384 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!region.isZero());
385 region.store(Address.zero(),NEXT_REGION_OFFSET);
386 }
387
388 /**
389 * @param region The bump-pointer region
390 * @return The DATA_END address from the region header
391 */
392 @Inline
393 public static Address getDataEnd(Address region) {
394 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!region.isZero());
395 return region.plus(DATA_END_OFFSET).loadAddress();
396 }
397
398 /**
399 * @param region The bump-pointer region
400 * @param endAddress The new DATA_END address from the region header
401 */
402 public static void setDataEnd(Address region, Address endAddress) {
403 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!region.isZero());
404 region.store(endAddress, DATA_END_OFFSET);
405 if (VERBOSE) {
406 Log.write("setDataEnd(");
407 Log.write(region);
408 Log.write(",");
409 Log.write(endAddress);
410 Log.writeln(")");
411 }
412 }
413
414 /**
415 * Return the end address of the given region.
416 * @param region The region.
417 * @return the allocation limit of the region.
418 */
419 public static Address getRegionLimit(Address region) {
420 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!region.isZero());
421 return region.plus(REGION_LIMIT_OFFSET).loadAddress();
422 }
423
424 /**
425 * Return the end address of the given region.
426 * @param region The region.
427 * @return the allocation limit of the region.
428 */
429 public static void setRegionLimit(Address region, Address limit) {
430 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!region.isZero());
431 region.plus(REGION_LIMIT_OFFSET).store(limit);
432 }
433
434 /**
435 * @param region The region.
436 * @return {@code true} if the address is region-aligned
437 */
438 public static boolean isRegionAligned(Address region) {
439 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!region.isZero());
440 return region.toWord().and(BLOCK_MASK).isZero();
441 }
442
443 /**
444 * Sanity check a region header
445 * @param region Region to check
446 */
447 public static void checkRegionMetadata(Address region) {
448 if (VM.VERIFY_ASSERTIONS) {
449 Address nextRegion = getNextRegion(region);
450 Address dataStart = getDataStart(region);
451 Address dataEnd = getDataEnd(region);
452 Address regionLimit = getRegionLimit(region);
453
454 VM.assertions._assert(nextRegion.isZero() || isRegionAligned(nextRegion));
455 VM.assertions._assert(dataEnd.GE(dataStart));
456 if (dataEnd.GT(regionLimit)) {
457 Log.write("dataEnd="); Log.write(dataEnd);
458 Log.write(", regionLimit="); Log.writeln(regionLimit);
459 }
460 VM.assertions._assert(dataEnd.LE(regionLimit));
461 VM.assertions._assert(regionLimit.EQ(region.plus(BLOCK_SIZE)));
462 }
463
464 }
465 /**
466 * Update the metadata to reflect the addition of a new region.
467 *
468 * @param start The start of the new region
469 * @param size The size of the new region (rounded up to block-alignment)
470 */
471 @Inline
472 private void updateMetaData(Address start, Extent size, int bytes) {
473 if (initialRegion.isZero()) {
474 /* this is the first allocation */
475 initialRegion = start;
476 region = start;
477 cursor = region.plus(DATA_START_OFFSET);
478 } else if (limit.NE(start) ||
479 region.diff(start.plus(size)).toWord().toExtent().GT(maximumRegionSize())) {
480 /* non contiguous or over-size, initialize new region */
481 setNextRegion(region,start);
482 setDataEnd(region,cursor);
483 region = start;
484 cursor = start.plus(DATA_START_OFFSET);
485 }
486 updateLimit(start.plus(size), start, bytes);
487 setRegionLimit(region,limit);
488 }
489
490 /**
491 * Gather data for GCspy. <p>
492 * This method calls the drivers linear scanner to scan through
493 * the objects allocated by this bump pointer.
494 *
495 * @param driver The GCspy driver for this space.
496 */
497 public void gcspyGatherData(LinearSpaceDriver driver) {
498 //driver.setRange(space.getStart(), cursor);
499 driver.setRange(space.getStart(), limit);
500 this.linearScan(driver.getScanner());
501 }
502
503 /**
504 * Gather data for GCspy. <p>
505 * This method calls the drivers linear scanner to scan through
506 * the objects allocated by this bump pointer.
507 *
508 * @param driver The GCspy driver for this space.
509 * @param scanSpace The space to scan
510 */
511 public void gcspyGatherData(LinearSpaceDriver driver, Space scanSpace) {
512 //TODO can scanSpace ever be different to this.space?
513 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(scanSpace == space, "scanSpace != space");
514
515 //driver.setRange(scanSpace.getStart(), cursor);
516 Address start = scanSpace.getStart();
517 driver.setRange(start, limit);
518
519 if (false) {
520 Log.write("\nBumpPointer.gcspyGatherData set Range "); Log.write(scanSpace.getStart());
521 Log.write(" to "); Log.writeln(limit);
522 Log.write("BumpPointergcspyGatherData scan from "); Log.writeln(initialRegion);
523 }
524
525 linearScan(driver.getScanner());
526 }
527
528
529 /**
530 * Perform a linear scan through the objects allocated by this bump pointer.
531 *
532 * @param scanner The scan object to delegate scanning to.
533 */
534 @Inline
535 public final void linearScan(LinearScan scanner) {
536 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(allowScanning);
537 /* Has this allocator ever allocated anything? */
538 if (initialRegion.isZero()) return;
539
540 /* Loop through active regions or until the last region */
541 Address start = initialRegion;
542 while (!start.isZero()) {
543 scanRegion(scanner, start); // Scan this region
544 start = getNextRegion(start); // Move on to next
545 }
546 }
547
548 /**
549 * Perform a linear scan through a single contiguous region
550 *
551 * @param scanner The scan object to delegate to.
552 * @param start The start of this region
553 */
554 @Inline
555 private void scanRegion(LinearScan scanner, Address start) {
556 /* Get the end of this region */
557 Address dataEnd = start.plus(DATA_END_OFFSET).loadAddress();
558
559 /* dataEnd = zero represents the current region. */
560 Address currentLimit = (dataEnd.isZero() ? cursor : dataEnd);
561 if (currentLimit.EQ(start.plus(DATA_END_OFFSET).plus(BYTES_IN_ADDRESS))) {
562 /* Empty region, so we can not call getObjectFromStartAddress() */
563 return;
564 }
565
566 ObjectReference current = VM.objectModel.getObjectFromStartAddress(start.plus(DATA_START_OFFSET));
567
568 /* Loop through each object up to the limit */
569 do {
570 /* Read end address first, as scan may be destructive */
571 Address currentObjectEnd = VM.objectModel.getObjectEndAddress(current);
572 scanner.scan(current);
573 if (currentObjectEnd.GE(currentLimit)) {
574 /* We have scanned the last object */
575 break;
576 }
577 /* Find the next object from the start address (dealing with alignment gaps, etc.) */
578 ObjectReference next = VM.objectModel.getObjectFromStartAddress(currentObjectEnd);
579 if (VM.VERIFY_ASSERTIONS) {
580 /* Must be monotonically increasing */
581 VM.assertions._assert(next.toAddress().GT(current.toAddress()));
582 }
583 current = next;
584 } while (true);
585 }
586
587 /**
588 * Some pages are about to be re-used to satisfy a slow path request.
589 * @param pages The number of pages.
590 */
591 protected void reusePages(int pages) {
592 VM.assertions.fail("Subclasses that reuse regions must override this method.");
593 }
594
595 /**
596 * Maximum size of a single region. Important for children that implement
597 * load balancing or increments based on region size.
598 * @return the maximum region size
599 */
600 protected Extent maximumRegionSize() { return Extent.max(); }
601
602 /** @return the current cursor value */
603 public final Address getCursor() { return cursor; }
604 /** @return the space associated with this bump pointer */
605 @Override
606 public final Space getSpace() { return space; }
607
608 /**
609 * Print out the status of the allocator (for debugging)
610 */
611 public final void show() {
612 Log.write("cursor = "); Log.write(cursor);
613 if (allowScanning) {
614 Log.write(" region = "); Log.write(region);
615 }
616 Log.write(" limit = "); Log.writeln(limit);
617 }
618 }