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.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 * Return the space this allocator is currently bound to.
045 *
046 * @return The Space.
047 */
048 protected abstract Space getSpace();
049
050 /**
051 * Aligns up an allocation request. The allocation request accepts a
052 * region, that must be at least particle aligned, an alignment
053 * request (some power of two number of particles) and an offset (a
054 * number of particles). There is also a knownAlignment parameter to
055 * allow a more optimised check when the particular allocator in use
056 * always aligns at a coarser grain than individual particles, such
057 * as some free lists.
058 *
059 * @param region The region to align up.
060 * @param alignment The requested alignment
061 * @param offset The offset from the alignment
062 * @param knownAlignment The statically known minimum alignment.
063 * @return The aligned up address.
064 */
065 @Inline
066 public static Address alignAllocation(Address region, int alignment, int offset, int knownAlignment, boolean fillAlignmentGap) {
067 if (VM.VERIFY_ASSERTIONS) {
068 VM.assertions._assert(knownAlignment >= MIN_ALIGNMENT);
069 VM.assertions._assert(MIN_ALIGNMENT >= BYTES_IN_INT);
070 VM.assertions._assert(!(fillAlignmentGap && region.isZero()));
071 VM.assertions._assert(alignment <= MAX_ALIGNMENT);
072 VM.assertions._assert(offset >= 0);
073 VM.assertions._assert(region.toWord().and(Word.fromIntSignExtend(MIN_ALIGNMENT-1)).isZero());
074 VM.assertions._assert((alignment & (MIN_ALIGNMENT - 1)) == 0);
075 VM.assertions._assert((offset & (MIN_ALIGNMENT - 1)) == 0);
076 }
077
078 // No alignment ever required.
079 if (alignment <= knownAlignment || MAX_ALIGNMENT <= MIN_ALIGNMENT)
080 return region;
081
082 // May require an alignment
083 Word mask = Word.fromIntSignExtend(alignment - 1);
084 Word negOff = Word.fromIntSignExtend(-offset);
085 Offset delta = negOff.minus(region.toWord()).and(mask).toOffset();
086
087 if (fillAlignmentGap && ALIGNMENT_VALUE != 0) {
088 if ((MAX_ALIGNMENT - MIN_ALIGNMENT) == BYTES_IN_WORD) {
089 // At most a single hole
090 if (delta.toInt() == (BYTES_IN_WORD)) {
091 region.store(Word.fromIntSignExtend(ALIGNMENT_VALUE));
092 region = region.plus(delta);
093 return region;
094 }
095 } else {
096 while (delta.toInt() >= (BYTES_IN_WORD)) {
097 region.store(Word.fromIntSignExtend(ALIGNMENT_VALUE));
098 region = region.plus(BYTES_IN_WORD);
099 delta = delta.minus(BYTES_IN_WORD);
100 }
101 }
102 }
103
104 return region.plus(delta);
105 }
106
107 /**
108 * Fill the specified region with the alignment value.
109 *
110 * @param start The start of the region.
111 * @param end A pointer past the end of the region.
112 */
113 @Inline
114 public static void fillAlignmentGap(Address start, Address end) {
115 if ((MAX_ALIGNMENT - MIN_ALIGNMENT) == BYTES_IN_INT) {
116 // At most a single hole
117 if (!end.diff(start).isZero()) {
118 start.store(ALIGNMENT_VALUE);
119 }
120 } else {
121 while (start.LT(end)) {
122 start.store(ALIGNMENT_VALUE);
123 start = start.plus(BYTES_IN_INT);
124 }
125 }
126 }
127
128 /**
129 * Aligns up an allocation request. The allocation request accepts a
130 * region, that must be at least particle aligned, an alignment
131 * request (some power of two number of particles) and an offset (a
132 * number of particles).
133 *
134 * @param region The region to align up.
135 * @param alignment The requested alignment
136 * @param offset The offset from the alignment
137 * @return The aligned up address.
138 */
139 @Inline
140 public static Address alignAllocation(Address region, int alignment, int offset) {
141 return alignAllocation(region, alignment, offset, MIN_ALIGNMENT, true);
142 }
143
144 /**
145 * Aligns up an allocation request. The allocation request accepts a
146 * region, that must be at least particle aligned, an alignment
147 * request (some power of two number of particles) and an offset (a
148 * number of particles).
149 *
150 * @param region The region to align up.
151 * @param alignment The requested alignment
152 * @param offset The offset from the alignment
153 * @return The aligned up address.
154 */
155 @Inline
156 public static Address alignAllocationNoFill(Address region, int alignment, int offset) {
157 return alignAllocation(region, alignment, offset, MIN_ALIGNMENT, false);
158 }
159
160 /**
161 * This method calculates the minimum size that will guarantee the allocation
162 * of a specified number of bytes at the specified alignment.
163 *
164 * @param size The number of bytes (not aligned).
165 * @param alignment The requested alignment (some factor of 2).
166 */
167 @Inline
168 public static int getMaximumAlignedSize(int size, int alignment) {
169 return getMaximumAlignedSize(size, alignment, MIN_ALIGNMENT);
170 }
171
172 /**
173 * This method calculates the minimum size that will guarantee the allocation
174 * of a specified number of bytes at the specified alignment.
175 *
176 * @param size The number of bytes (not aligned).
177 * @param alignment The requested alignment (some factor of 2).
178 * @param knownAlignment The known minimum alignment. Specifically for use in
179 * allocators that enforce greater than particle alignment. It is a <b>precondition</b>
180 * that size is aligned to knownAlignment, and that knownAlignment >= MIN_ALGINMENT.
181 */
182 @Inline
183 public static int getMaximumAlignedSize(int size, int alignment, int knownAlignment) {
184 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(size == Conversions.roundDown(size, knownAlignment));
185 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(knownAlignment >= MIN_ALIGNMENT);
186
187 if (MAX_ALIGNMENT <= MIN_ALIGNMENT || alignment <= knownAlignment) {
188 return size;
189 } else {
190 return size + alignment - knownAlignment;
191 }
192 }
193
194 /**
195 * Single slow path allocation attempt. This is called by allocSlow.
196 *
197 * @param bytes The size of the allocation request
198 * @param alignment The required alignment
199 * @param offset The alignment offset
200 * @return The start address of the region, or zero if allocation fails
201 */
202 protected abstract Address allocSlowOnce(int bytes, int alignment, int offset);
203
204 /**
205 * <b>Out-of-line</b> slow path allocation. This method forces slow path
206 * allocation to be out of line (typically desirable, but not when the
207 * calling context is already explicitly out-of-line).
208 *
209 * @param bytes The size of the allocation request
210 * @param alignment The required alignment
211 * @param offset The alignment offset
212 * @return The start address of the region, or zero if allocation fails
213 */
214 @NoInline
215 public final Address allocSlow(int bytes, int alignment, int offset) {
216 return allocSlowInline(bytes, alignment, offset);
217 }
218
219 /**
220 * <b>Inline</b> slow path allocation. This method attempts allocSlowOnce
221 * several times, and allows collection to occur, and ensures that execution
222 * safely resumes by taking care of potential thread/mutator context affinity
223 * changes. All allocators should use this as the trampoline for slow
224 * path allocation.
225 *
226 * @param bytes The size of the allocation request
227 * @param alignment The required alignment
228 * @param offset The alignment offset
229 * @return The start address of the region, or zero if allocation fails
230 */
231 @Inline
232 public final Address allocSlowInline(int bytes, int alignment, int offset) {
233 int gcCountStart = Stats.gcCount();
234 Allocator current = this;
235 Space space = current.getSpace();
236 for (int i = 0; i < Plan.MAX_COLLECTION_ATTEMPTS; i++) {
237 Address result = current.allocSlowOnce(bytes, alignment, offset);
238 if (!result.isZero()) {
239 return result;
240 }
241 if (!Plan.gcInProgress()) {
242 /* This is in case a GC occurs, and our mutator context is stale.
243 * In some VMs the scheduler can change the affinity between the
244 * current thread and the mutator context. This is possible for
245 * VMs that dynamically multiplex Java threads onto multiple mutator
246 * contexts, */
247 current = VM.activePlan.mutator().getAllocatorFromSpace(space);
248 }
249 }
250 Log.write("GC Error: Allocator.allocSlow failed on request of ");
251 Log.write(bytes);
252 Log.write(" on space ");
253 Log.writeln(space.getName());
254 Log.write("gcCountStart = ");
255 Log.writeln(gcCountStart);
256 Log.write("gcCount (now) = ");
257 Log.writeln(Stats.gcCount());
258 Space.printUsageMB();
259 VM.assertions.fail("Allocation Failed!");
260 /* NOTREACHED */
261 return Address.zero();
262 }
263 }