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