001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Common Public License (CPL);
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/cpl1.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.plan.Plan;
016 import org.mmtk.policy.Space;
017 import org.mmtk.utility.*;
018 import org.mmtk.utility.statistics.*;
019
020 import org.mmtk.vm.VM;
021
022 import org.vmmagic.unboxed.*;
023 import org.vmmagic.pragma.*;
024
025 /**
026 * This abstract base class provides the basis for processor-local
027 * allocation. The key functionality provided is the retry mechanism
028 * that is necessary to correctly handle the fact that a "slow-path"
029 * allocation can cause a GC which violate the uninterruptability assumption.
030 * This results in the thread being moved to a different processor so that
031 * the allocator object it is using is not actually the one for the processor
032 * it is running on.
033 *
034 * This class also includes functionality to assist allocators with
035 * ensuring that requests are aligned according to requests.
036 *
037 * Failing to handle this properly will lead to very hard to trace bugs
038 * where the allocation that caused a GC or allocations immediately following
039 * GC are run incorrectly.
040 */
041 @Uninterruptible public abstract class Allocator implements Constants {
042
043 /**
044 * Aligns up an allocation request. The allocation request accepts a
045 * region, that must be at least particle aligned, an alignment
046 * request (some power of two number of particles) and an offset (a
047 * number of particles). There is also a knownAlignment parameter to
048 * allow a more optimised check when the particular allocator in use
049 * always aligns at a coarser grain than individual particles, such
050 * as some free lists.
051 *
052 * @param region The region to align up.
053 * @param alignment The requested alignment
054 * @param offset The offset from the alignment
055 * @param knownAlignment The statically known minimum alignment.
056 * @return The aligned up address.
057 */
058 @Inline
059 public static Address alignAllocation(Address region, int alignment, int offset, int knownAlignment, boolean fillAlignmentGap) {
060 if (VM.VERIFY_ASSERTIONS) {
061 VM.assertions._assert(knownAlignment >= MIN_ALIGNMENT);
062 VM.assertions._assert(MIN_ALIGNMENT >= BYTES_IN_INT);
063 VM.assertions._assert(!(fillAlignmentGap && region.isZero()));
064 VM.assertions._assert(alignment <= MAX_ALIGNMENT);
065 VM.assertions._assert(offset >= 0);
066 VM.assertions._assert(region.toWord().and(Word.fromIntSignExtend(MIN_ALIGNMENT-1)).isZero());
067 VM.assertions._assert((alignment & (MIN_ALIGNMENT - 1)) == 0);
068 VM.assertions._assert((offset & (MIN_ALIGNMENT - 1)) == 0);
069 }
070
071 // No alignment ever required.
072 if (alignment <= knownAlignment || MAX_ALIGNMENT <= MIN_ALIGNMENT)
073 return region;
074
075 // May require an alignment
076 Word mask = Word.fromIntSignExtend(alignment - 1);
077 Word negOff = Word.fromIntSignExtend(-offset);
078 Offset delta = negOff.minus(region.toWord()).and(mask).toOffset();
079
080 if (fillAlignmentGap && ALIGNMENT_VALUE != 0) {
081 if ((MAX_ALIGNMENT - MIN_ALIGNMENT) == BYTES_IN_WORD) {
082 // At most a single hole
083 if (delta.toInt() == (BYTES_IN_WORD)) {
084 region.store(Word.fromIntSignExtend(ALIGNMENT_VALUE));
085 region = region.plus(delta);
086 return region;
087 }
088 } else {
089 while (delta.toInt() >= (BYTES_IN_WORD)) {
090 region.store(Word.fromIntSignExtend(ALIGNMENT_VALUE));
091 region = region.plus(BYTES_IN_WORD);
092 delta = delta.minus(BYTES_IN_WORD);
093 }
094 }
095 }
096
097 return region.plus(delta);
098 }
099
100 /**
101 * Fill the specified region with the alignment value.
102 *
103 * @param start The start of the region.
104 * @param end A pointer past the end of the region.
105 */
106 @Inline
107 public static void fillAlignmentGap(Address start, Address end) {
108 if ((MAX_ALIGNMENT - MIN_ALIGNMENT) == BYTES_IN_INT) {
109 // At most a single hole
110 if (!end.diff(start).isZero()) {
111 start.store(ALIGNMENT_VALUE);
112 }
113 } else {
114 while (start.LT(end)) {
115 start.store(ALIGNMENT_VALUE);
116 start = start.plus(BYTES_IN_INT);
117 }
118 }
119 }
120
121 /**
122 * Aligns up an allocation request. The allocation request accepts a
123 * region, that must be at least particle aligned, an alignment
124 * request (some power of two number of particles) and an offset (a
125 * number of particles).
126 *
127 * @param region The region to align up.
128 * @param alignment The requested alignment
129 * @param offset The offset from the alignment
130 * @return The aligned up address.
131 */
132 @Inline
133 public static Address alignAllocation(Address region, int alignment, int offset) {
134 return alignAllocation(region, alignment, offset, MIN_ALIGNMENT, true);
135 }
136
137 /**
138 * Aligns up an allocation request. The allocation request accepts a
139 * region, that must be at least particle aligned, an alignment
140 * request (some power of two number of particles) and an offset (a
141 * number of particles).
142 *
143 * @param region The region to align up.
144 * @param alignment The requested alignment
145 * @param offset The offset from the alignment
146 * @return The aligned up address.
147 */
148 @Inline
149 public static Address alignAllocationNoFill(Address region, int alignment, int offset) {
150 return alignAllocation(region, alignment, offset, MIN_ALIGNMENT, false);
151 }
152
153 /**
154 * This method calculates the minimum size that will guarantee the allocation
155 * of a specified number of bytes at the specified alignment.
156 *
157 * @param size The number of bytes (not aligned).
158 * @param alignment The requested alignment (some factor of 2).
159 */
160 @Inline
161 public static int getMaximumAlignedSize(int size, int alignment) {
162 return getMaximumAlignedSize(size, alignment, MIN_ALIGNMENT);
163 }
164
165 /**
166 * This method calculates the minimum size that will guarantee the allocation
167 * of a specified number of bytes at the specified alignment.
168 *
169 * @param size The number of bytes (not aligned).
170 * @param alignment The requested alignment (some factor of 2).
171 * @param knownAlignment The known minimum alignment. Specifically for use in
172 * allocators that enforce greater than particle alignment. It is a <b>precondition</b>
173 * that size is aligned to knownAlignment, and that knownAlignment >= MIN_ALGINMENT.
174 */
175 @Inline
176 public static int getMaximumAlignedSize(int size, int alignment, int knownAlignment) {
177 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(size == Conversions.roundDown(size, knownAlignment));
178 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(knownAlignment >= MIN_ALIGNMENT);
179
180 if (MAX_ALIGNMENT <= MIN_ALIGNMENT || alignment <= knownAlignment) {
181 return size;
182 } else {
183 return size + alignment - knownAlignment;
184 }
185 }
186
187 /**
188 * Single slow path allocation attempt. This is called by allocSlow.
189 *
190 * @param bytes The size of the allocation request
191 * @param alignment The required alignment
192 * @param offset The alignment offset
193 * @return The start address of the region, or zero if allocation fails
194 */
195 protected abstract Address allocSlowOnce(int bytes, int alignment, int offset);
196
197 /**
198 * <b>Out-of-line</b> slow path allocation. This method forces slow path
199 * allocation to be out of line (typically desirable, but not when the
200 * calling context is already explicitly out-of-line).
201 *
202 * @param bytes The size of the allocation request
203 * @param alignment The required alignment
204 * @param offset The alignment offset
205 * @return The start address of the region, or zero if allocation fails
206 */
207 @NoInline
208 public final Address allocSlow(int bytes, int alignment, int offset) {
209 return allocSlowInline(bytes, alignment, offset);
210 }
211
212 /**
213 * <b>Inline</b> slow path allocation. This method attempts allocSlowOnce
214 * several times, and allows collection to occur, and ensures that execution
215 * safely resumes by taking care of potential thread/mutator context affinity
216 * changes. All allocators should use this as the trampoline for slow
217 * path allocation.
218 *
219 * @param bytes The size of the allocation request
220 * @param alignment The required alignment
221 * @param offset The alignment offset
222 * @return The start address of the region, or zero if allocation fails
223 */
224 @Inline
225 public final Address allocSlowInline(int bytes, int alignment, int offset) {
226 int gcCountStart = Stats.gcCount();
227 Allocator current = this;
228 for (int i = 0; i < Plan.MAX_COLLECTION_ATTEMPTS; i++) {
229 Address result = current.allocSlowOnce(bytes, alignment, offset);
230 if (!result.isZero()) {
231 return result;
232 }
233 if (!Plan.gcInProgress()) {
234 /* This is in case a GC occurs, and our mutator context is stale.
235 * In some VMs the scheduler can change the affinity between the
236 * current thread and the mutator context. This is possible for
237 * VMs that dynamically multiplex Java threads onto multiple mutator
238 * contexts, */
239 current = VM.activePlan.mutator().getOwnAllocator(current);
240 }
241 }
242 Log.write("GC Error: Allocator.allocSlow failed on request of ");
243 Log.write(bytes);
244 Log.write(" on space ");
245 Log.writeln(Plan.getSpaceNameFromAllocatorAnyLocal(this));
246 Log.write("gcCountStart = ");
247 Log.writeln(gcCountStart);
248 Log.write("gcCount (now) = ");
249 Log.writeln(Stats.gcCount());
250 Space.printUsageMB();
251 VM.assertions.fail("Allocation Failed!");
252 /* NOTREACHED */
253 return Address.zero();
254 }
255 }